若干タイトル詐欺で、計算量理論と暗号理論で扱う問題の種類がなぜ違うのか？という自分が長い間感じていたが調べたり考えたりせずに放置していた疑問の話をする。あと厳密にはタイトルの言っていることは誤りだと思っていて、計算量理論の入門的な講義を受けた後に出る感想を想定している（もっと高度な講義なら、離散対数問題を扱う場合もあるかな？と思うため）。
計算複雑性の入門的な講義や、アルゴリズムとデータ構造の講義を受けたとする。すると、例えばNP完全問題ってのがあってハミルトン閉路問題とかがあるみたいなことを勉強することになる。P問題とNP問題の関係性とかNP完全問題の帰着とかを勉強すると、それで半期の講義が終了する。ところで、そういえば離散対数問題が難しいからそれが暗号とかに使われてるとか聞いたことあるな、でも授業で出てこない、みたいなことが起こる。
このような現象が起きるのは、計算量理論で扱われる問題の難しさと、暗号理論で扱われる問題の難しさの間にギャップが存在しているからである。
最悪時困難性と平均時困難性
計算量理論における難しさは基本的には最悪計算量の意味でで捉えられる（最悪時困難性）。この概念は、ある問題を解くにあたって最も都合の悪い入力に対するアルゴリズムの計算時間で、その問題の難しさを捉えるという方法である。一方で、暗号理論における難しさは平均計算量の意味で捉えられる（平均時困難性）。この概念は、ある分布から問題の入力がランダムに生成される場合のアルゴリズムの期待計算時間によって、その問題の難しさを捉えるという方法である。
競技プログラミング等ではある問題について、すべての入力について制限時間内に解が求められるようなアルゴリズムを設計することが目標となるため、最悪計算量で考えることが大事になる。
しかしながら、現実の応用例の中には、最悪計算量となってしまうようなコーナーケースが無視できるような確率であれば、必ずしも最悪計算量で考えなくてもよく、平均的によく解くことができればよいという場合も考えられる。問題の入力に対する計算時間の分布がロングテールでないことがわかっているとか、期待される場合にはこの考え方でも十分有用なはずである。
暗号の設計に適切な困難性はどちらか
さて、暗号を設計する場合に安全性の要件として要求するのはどちらにするのが良いだろう？
暗号の安全性要件として最悪時困難性を採用する場合を考えてみる。この場合、どんなアルゴリズムにとってもコーナーケースとなるような入力を鍵の生成に使うことになるが、そのようなコーナーケースを設計することはできないはずである。困難性の仮定の中に入力インスタンスの設計方法への言及はない。一方で、平均時困難性を安全性の要件として採用すれば、問題の入力の分布の生成方法に依存する、つまり設計可能性に言及されている形で安全性の担保ができて嬉しいということになる。
なお、平均だと安全ではないような入力がたくさん存在し得るんじゃないか？というような気もしてくるが、「ある問題が平均的に多項式時間で解ける」ということが「あるパラメータに対して、それに依存する多項式時間を超えるような入力となってしまう確率が、そのパラメータの逆数に比例して小さい確率になる」みたいなことと同値になることがわかっているため、そのパラメータを大きくすれば、安全にならないような入力が稀にしか起こらないことがいえる。
最悪時困難性を暗号の安全性保証に使いたい：耐量子暗号の構成に向けて
ところで、問題によっては、最悪計算量の意味で難しい問題から平均計算量の意味で難しい問題を構成できることが知られている。ということは、例えばNP困難な問題から構成できる平均計算量の意味で難しい問題があれば、その問題を暗号の設計に利用することで、非常に強い暗号が作れそうなことがわかる。NP困難な問題は量子計算でも効率的に解けないと考えられているので、耐量子暗号が作れるということになる。
このアイデアが使われているのが格子暗号といわれるグループの暗号たちである。格子暗号の多くの安全性に仮定されているLWE問題は、SVP問題というNP困難な問題...ではなくその近似問題を変換することでつくられる問題になっている。この近似が厳しいものであればNP困難に近く、緩ければ多項式時間で解かれてしまう。したがって、できるだけ近い近似問題を利用できればよいが、現状ではNP困難ではなく、クラスPでもない間の領域の近似が使われている。なお、その近似の程度が厳密にどのクラスに属しているものであるかは未解決問題となっている。
ところで離散対数問題はどの計算量クラスか
離散対数問題はNP-intermediateとよばれるクラス（NPに入るがNP困難でもPでもない）に属していると考えられている。暗号の安全性仮定に利用されている問題の多くはこのクラスの問題を利用している。多項式時間で解けてしまうことが分かっているような問題（クラスPに属する問題）を使うと安全性的にはマズいが、それより難しい問題で、入力の設計がしやすい問題の1つが離散対数問題含め、暗号に利用されている問題だといえると思う。
まとめ
ということで、結局言いたかったのは、次の2つに要約される。
計算量理論は最悪計算量で考える理論。計算量理論はNPとかPとかクラスのどこに問題が属するか、みたいな特徴づけや問題同士の関係性が知りたくて、問題の入力の作り方は気にしない。
暗号理論は平均計算量で考える理論。暗号理論は問題の入力を作る必要があって、ある程度難しいことがわかっていて、入力が効率的に設計できるような問題を利用しているので、そういう問題を使った議論が主になる。
