配分額：26000000円 （ 直接経費：20000000円 、 間接経費：6000000円 ）

researchmap

学習アルゴリズムが予測のために⽤いる仮説の記述の簡潔さと、その仮説を発⾒するために必要となる計算量、及び、学習アルゴリズムの能⼒に対する理論保証とデータの圧縮可能性の関係の解析を中⼼とした研究を⾏います。得られた結果を元に、NP 困難性に基づく暗号の安全性証明という重要未解決問題の本質的進展と、理論計算機科学のアイデアを取り込んだ⾰新的学習アルゴリズム構成・活⽤法の創出を⽬指します。

researchmap

配分額：2860000円 （ 直接経費：2200000円 、 間接経費：660000円 ）

本研究の目的は一方向性関数をNP問題の困難性から構成するという重要未解決問題の解決に向けて，現在知られている証明手法の障壁である，相対化の障壁の突破を目指した研究を行うことである．その目的の達成に向けて，従来の研究に証明系の観点を加えた研究を進めている．本年度の成果は大きく2つ，(i)一方向性関数の非存在下で成立する学習論的性質の改善と(ii)知識複雑さに基づく課題達成への新しいアプローチの提案である．
(i)一方向性関数の非存在下で成立する学習論的性質の改善について，これまでに得られていた一方向性関数の非存在下で成立する学習論的アルゴリズム的性質を改善し，かつ従来のものよりクリアな理論を構築することに成功した．一方向性関数をNP問題の困難性から構成するという課題は，一方向性関数の非存在下で成立するアルゴリズム的性質をNP完全問題を効率的に解ける領域まで強化するという課題に他ならないため，この成果は課題解決に向けた１つの重要な進展となる結果である．当該研究は理論計算機科学のトップ国際会議であるFOCS2023に採択され，発表を行った．
(ii)知識計算量に基づく課題達成への新しいアプローチの提案は研究提案書項目Cに関しての進展を与える成果である．これはGapMCSPと呼ばれる計算問題に対して知識複雑さゼロ(ゼロ知識)あるいは対数的知識複雑さの対話証明系を与えることが一方向性関数をNP問題の困難性から構成することを特徴付けることを証明したものであり，これに基づき問題に対する知識計算量を改善していくというアプローチを提案した．この方向は対話証明系に対して知られている相対化の障壁を突破する手法が組み込みやすいことが期待されるアプローチであるという点で重要な結果である．当該研究は理論計算機科学のトップ国際会議であるSTOC2024に採択済みである．

researchmap

配分額：40560000円 （ 直接経費：31200000円 、 間接経費：9360000円 ）

量子計算を使用する上で本質的になると予想される３つの分野（委託量子計算・分散量子計算・単体量子計算）について研究を進めた．
委託量子計算分野に関しては，セキュリティの基礎となる，一方向性関数，コミットメント，電子署名等に関する成果を得た．具体的には，古典暗号の場合は一方向性関数が最も基礎的な仮定であるが、量子を用いた暗号の場合は必ずしもそうではないことを示した。特に、量子通信をもちいたコミットメント、電子署名について、一方向性関数よりも弱い仮定と考えられている疑似ランダム量子状態を用いて構成した。また、古典では構成方法が知られていない仮定から公開鍵暗号を構成する方法を提示し，さらに，コミットメントの安全性の等価性を示した。
分散量子計算の分野では，量子非対話型証明および量子対話型証明についてネットワーク上に量子計算機が分散的に存在するような環境（分散的環境）での研究を進めた．分散型量子対話型証明においては通常の分散的でない場合と同様に，一般的なプロトコルを定数ラウンドのプロトコルに変換する方法を示すことができた．また分散型量子非対話型証明においては量子状態生成の検証という新しい文脈で効率的なプロトコルを開発した．
単体量子計算の分野では，グラフ彩色問題に対する指数時間量子アルゴリズムを開発した。現在知られている最速の古典アルゴリズムは n 頂点グラフの彩色数の計算に Ω(2^n) 時間かかる。本研究では O(1.914^n) 時間の量子アルゴリズムを開発した。また、無線通信における最適化問題を効率的に解く量子アルゴリズムを提案した。さらに，使用可能な量子メモリ量に制限がある場合において，ポストセレクションを任意のタイミングで許しても，計算の最後にのみ許した場合と比べて計算能力に変わりがなく，量子メモリ量の制限が計算能力に本質的に大きな影響を与えることを示す結果を得た．

researchmap

配分額：1100000円 （ 直接経費：1100000円 ）

本年度は，暗号理論と計算複雑さ理論の中心的概念であるNPの最悪時困難性の間にある諸概念と学習の計算論的困難性（以下，学習困難性と呼ぶ）の関係性を調査し，暗号・計算・学習の理論をまたぐ，以下の重要な関係性を得た．
(1) 平均時学習困難性と追加入力付き暗号一方向性関数の等価性 :追加入力付き暗号一方向性関数とは，標準的な暗号の安全性要件を自然に弱めた暗号プリミティブである．既存研究では，そのような追加入力付き暗号一方向性関数の存在が，学習困難性を示すのに十分であることが知られていた．本研究では従来の学習モデルの要件を平均時に緩和したモデルを導入し，既存研究の逆方向，すなわち，平均時学習困難性が追加入力付き暗号一方向性関数の存在に必要十分であることを証明した．
(2) NPの平均時容易性を基にした，効率的学習可能性の証明：従来，計算論的学習理論で議論される学習要件は任意の関数を任意の分布上で学習するという最悪時の要件を持ち，この点が従来の暗号理論とのギャップの大きな要因となっていた．本研究ではそのような分布の条件を任意の分布から任意の回路モデルで効率的にサンプル可能な分布に緩和することで，そのようなモデルにおける十分自然でかつ強い学習可能性が，NPの平均時容易性のみから従うことを証明した．加えて，平均時容易性を基にした学習可能性の証明において，このような分布条件の緩和が，相対化する手法と呼ばれる現在の標準的証明手法の枠組みの中で本質的に不可欠であるという理論的根拠を与えた．

researchmap