平均計算量と暗号の安全性について

研究

Computational Complexity Weblog の2/14の記事を発端に 186::Diary や 偽らざるもの でも話題になっていますが，worst/average-case connection を持つ問題を暗号のベースとすることについての是非について私見を少し述べたいと思います．186::Diary でコメントしたように worst/average-case connection を持つかどうか以前に暗号に利用可能な時点で計算困難性（例えばNP困難）を保証することは相当難しいのです．例えば暗号に要請される最も基本的な機能である一方向性ですらかなり難しいのではと個人的には考えています．（もちろんこの考えは私のオリジナルではなく，そのような考えを支持するような結果がいくつか発表されています．）

簡単な場合でなぜそう考えられるかを見てみましょう．あるNP困難な判定問題Lが一方向性置換族f={f_n}の（平均的）逆計算問題に多項式時間帰着できたと仮定します．ただし簡単のためその帰着Rは決定性でかつ非適応的（つまり fの逆計算オラクルには一回しか質問を行わない）とします．（言い換えると平均的にfの逆計算が行えるアルゴリズムIの存在を仮定してIをオラクルとしたRがL を多項式時間で正しく判定可能とします．）このような帰着Rが存在した場合，coNPがNPに含まれます．

直観的な証明を与えてみます．coNP完全問題L'を考えて，これを解く非決定性多項式時間アルゴリズムAを帰着Rから構成します．任意のインスタンスxについてアルゴリズムAは以下のような動作を行います．

  1. R(x)をシミュレートする．Rが逆計算オラクルIに途中で行う質問（一回）の回答は非決定性計算を使って用意する．
  2. R(x)=NO ならYESと出力，R(x)=YESならNOと出力する．

これでNP計算でcoNP完全問題が計算できていることが確認できます．Rが確率的な場合にも割とすぐに拡張でき，その場合の結論は，coAMがAMに含まれる，に変化します．アイデアは最初のラウンドで検証者が帰着Rで使う乱数を証明者に渡すという点です．あとはほとんど決定性の場合と同じです．

多くの計算量理論の研究者はNPはcoNP（あるいはAMはcoAM）を完全には包含しないと予想しているので，このようにNP困難問題ベースの一方向性置換を作ることは難しそうです．さらに一般的な場合，例えば一方向性置換ではなく一方向性関数の場合，や帰着アルゴリズムの行う質問が適応的であった場合などがあるわけですが，それらに関してもいくつか否定的な結果が知られています．その結果は

  • A. Akavia, O. Goldreich, S. Goldwasser, and D. Moshkovitz
    • On Basing One-Way Functions on NP-Hardness, STOC 2006.

で示されています．結果だけ言えば，

  • 逆像サイズ検証可能な一方向性関数（例えば regular one-way function）の逆計算問題がNP困難問題に適応的な質問を使って確率的多項式時間帰着可能であれば coAM が AM に含まれる．
  • 一般の一方向性関数の逆計算問題がNP困難問題に非適応的な質問だけで確率的多項式時間帰着可能であれば coAM が AM に含まれる．

ということを示しています．一般の一方向性関数に対しては適応的な帰着の場合は未解決ですが，結果的には同様の結論が得られるのではないかと予想しています．

では一方向性関数の難しさをNP困難まで引き上げることはやはり不可能なのか？というとそこまでは言い切ることはできません．というのもこれらの結果は全て black-box 帰着を想定しているからです．non-black-box 型の帰着に関しては既に素晴らしい結果がいくつか発表されていますが，新しい手法を開発するのは相当難しいため，non-black-box帰着による一方向性関数の難しさについてどこまでの進展があるかは今のところ何とも言えません．