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

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

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