学習階層の解析と計算論的学習理論の新展開

学习层次分析及计算学习理论新进展

基本信息

批准号：
21J11263
负责人：
七島幹人
金额：
$ 0.7万
依托单位：
Tokyo Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-28 至 2023-03-31
项目状态：
已结题

项目摘要

NPの最悪時困難性を基とした暗号理論の中核的概念である一方向性関数の構成に向け，第一年次に得られた学習困難性に着目した成果を踏まえた上で，以下のボトムアップ/トップダウン的アプローチによる研究を進めた．ボトムアップ的アプローチでは，最悪時困難性仮定を暗号の安全性に変換していくという動機のもと，第一年次の成果である，学習の最悪時困難性からNPの誤りなし平均時困難性への変換手法の拡張可能性について研究を行い，平均時誤りあり・誤りなし困難性，及び，学習困難性に関する新たな証明の障壁の明示化によって，真に課題解決に有効となり得る手法の特定を行った．トップダウン的アプローチでは，暗号の構成に必要な仮定を最悪時困難性仮定まで緩和していくという動機のもと，一方向性関数の非存在から従うアルゴリズム的性質の研究を進めた．第一年次では，一方向性関数の非存在から強い平均時学習可能性が従うことが明らかになっていた．本年度はそこでの手法を応用し，理論計算機科学の諸概念とのより広い関係が期待出来る抽象的概念である，情報の対称性に着目することで，一方向性関数の存在の新たな情報基礎論的特徴付けを得た．加えて，第一年次の成果を低複雑性クラス，特に，並列定数時間計算可能クラスに応用することで，暗号理論における重要プリミティブである並列定数時間計算可能多項式ストレッチ疑似乱数生成器の学習困難性を基にした新しい構成アプローチと特徴付けの結果を得た．

为了构建基于NP最坏情况难度的密码理论核心概念单向函数，基于第一年获得的学习难度结果，我们进行了以下研究。我们使用自下而上/自上而下的方法进行研究。在自下而上的方法中，出于将最坏情况难度假设转换为密码安全性的动机，我们将学习的最坏情况难度转换为 NP 的无错误平均时间难度，这是第一个的结果今年我们将研究转换方法对数据的可扩展性，并澄清关于平均时间无错误/无错误难度和学习难度的新证明障碍，以开发出真正有效解决问题的方法。我做了鉴定。在自上而下的方法中，出于将密码构造所需的假设放宽到最坏情况难度假设的动机，我们继续研究由于缺乏单向函数而产生的算法特性。在第一年，很明显，由于缺乏单向函数，因此具有很强的平均时间可学习性。今年，我们将应用在那里开发的方法，重点关注信息对称这一抽象概念，预计它将与理论计算机科学中的各种概念有更广泛的关系，从而为单向函数的存在创造一个新的信息基础。获得了理论表征。此外，通过将第一年的成果应用于低复杂度类，特别是并行常量时间可计算类，我们将解决并行常量时间可计算多项式拉伸伪随机数生成器的学习困难，这些生成器是数学中重要的原语。我们获得了基于性别的新的组合方法和表征结果。