NP【新歓ブログリレー2017 16日目】

こんばんは。成です。

CTF・競プロ体験会、お疲れ様でした！大盛況で終わってホッとしています。

今回はCTFに関連して、セキュリティに関わるNPについて書きたいと思います。

NPとは

NPとは、Non-deterministic Polynomial timeのことで、日本語で「非決定性多項式時間」と言います。これに対して、Pというのがあって、これはPolynomial time(多項式時間)のことです。

多項式時間というのは、通常のコンピュータ上で計算量が多項式なものです。例えばソートアルゴリズム $O (n l o g_{2} n)$ や、最長共通部分列アルゴリズム $O (n m)$ などがそうです。

逆に計算量が多項式でないものというのは、巡回セールスマン問題に対するHeld-Karpアルゴリズム $O (n^{2} 2^{n})$ や、0-1ナップザック問題 $O (2^{n})$ などがあります。

こういった $O (2^{n})$ が入った問題はだいたいNPです(すごい大雑把)。

厳密には、「全ての可能性を探索できる」コンピュータ上では多項式時間で計算可能なYes/No問題をクラスNPの問題と呼びます。

全ての可能性を探索できる、というのは、ナップザック問題でいえば「アイテムを使う/使わない」という2つの可能性を同時に探索できる、というものです。量子のように全ての可能性を重ね合わせで表現するなどすると実現できるかもしれない仮想のコンピュータです。

また、Yes/No問題なので、部分和問題 $O (2^{n})$ はYes/No問題なのでクラスNPですが、ナップザック問題は最適化問題のため厳密にはクラスNPではありません。ただし、ナップザック問題は例えば「価値の総和をある値以上にできるか？」というYes/No問題を用いて二分探索する方針にすると、クラスNPの問題を用いて解くことが可能となります。このようなナップザック問題のような問題はNP困難というクラスに属します。

NPの恐ろしさ

五十歩百歩ということわざがあります。

これは、50歩逃げても100歩逃げても、大体同じでしょ、という感じの意味のことわざです。

このように、たかが定数倍では特に大差無いように感じるわけです。これはコンピュータでもそうで、1000倍ぐらいだろうと定数倍なら脅威ではありません(スパコンを1000個用意すれば同じわけです)。

では、クラスNPはどうでしょう。量子コンピュータが無い場合、計算量は $O (2^{n})$ です。ここで「五十歩百歩」してみましょう。 $X = 2^{50}$ と $Y = 2^{100}$ の差を見ると、なんと $Y = X^{2}$ なわけです。

指数を数倍するだけで、全体の数は大幅に増加します。これがクラスNPの怖いところで、もし $n = 512$ について解かれてしまっても、 $n = 1024$ について解くには簡単に至らないわけです。

NPの解法

クラスNPに属する問題はどのように解けるのでしょうか？

有名なクラスNPの問題はナップザック問題です。これはよく動的計画法の説明で使われ、そこでは多項式時間で解けるように見えます。

しかし、このようなナップザック問題は、重さの総和が小さめに作られているために解けるわけで、重さに制限が無ければ動的計画法の手法は使えません。

クラスNPの問題は基本的に、全探索するしかありません。つまり、現実的な時間では計算不可能です。

ただし、問題の性質を良く見極めると計算量を若干ゃ下げることが可能です。

例えば、ナップザック問題や部分和問題は、半分全列挙を用いることで $O (2^{n / 2})$ 程度に抑えられます。

また、グラフの最大独立集合問題も、枝刈りを適切に行うことで、指数関数の底を2未満に抑えることが可能です。

さらに、クラスNPの問題の多くは整数計画問題として容易に記述でき、整数計画問題はそれ専用の枝刈り探索アルゴリズムがあるため、ある程度速めに解を求めることが可能です。

ただし上記の手法はどれも指数関数の域を出ないため、クラスNPであることに変わりなく、恐ろしさはそのままです。

ちょっと優しいNP

ところで、巡回セールスマン問題やナップザック問題に関しては、厳密な最適解を求めずとも、十分良い解が求まれば工業的応用という意味では十分です。そのために、ヒューリスティック解法等も多く研究されています。

最適解で無ければ、指数関数的時間計算量でないアルゴリズムも多数あります。良さそうな選択肢を連続的に選ぶアルゴリズムなどもヒューリスティックになりますが、そこそこ良い解を高速に求めることが可能です。

このヒューリスティックジャンルは、最適解を求めることが目的ではなく、いかに高速に良質な解を求めるかが目的になります。

NPの使われ方

こんな難しい問題ですが、いったいどのようなことに使われるのでしょうか？

例えば、ナップザック問題はどうでしょう。ナップザック問題は「どれだけ効率よく詰められるか？」という応用的側面がそのまま問題になっています。

また、巡回セールスマン問題も、「どれだけ効率よく巡回できるか？」という応用があります。ドリルの穴開け問題に応用することで、いかに効率よく基盤に穴をあけて生産能率を上げるかにも直結します。

さらにグラフの最小頂点被覆問題は、一般的なネットワークと関わりがあります。

このような工業的な応用も多いですが、現代で最も活躍しているのは、やはり暗号的分野でしょう。

NPと暗号

突然ですが、15を素因数分解してみてください。

簡単ですね。素因数は3と5です。

では、6319はどうでしょう。

これは、71と89です。暗算は難しいですね。

では、1000000016000000063は？

これは1000000007と1000000009です。人間には難しいでしょう。

このような素因数分解は、桁数 $n$ に対して計算量が指数になり、NP困難であると予想されています(クラスPとなるようなアルゴリズムが見つかっていない)。

では、また突然ですが、 $3 \times 5$ を計算してみてください。

15ですね。 $71 \times 89$ は？

6319です。 $1000000007 \times 1000000009$ は？

1000000016000000063。

これらはただの掛け算で、筆算すれば比較的簡単に求まります。

このように、素因数分解と掛け算には、逆操作の計算量が圧倒的に違うという性質があります。

すると、例えばある人が秘密の素数 $p, q$ を生成して、その積 $n = p q$ を公開しても、秘密の素数 $p, q$ はバレない、という一方向的な性質ができ、これとフェルマーの小定理(オイラーの定理)を組み合わせることで、有名なRSA暗号が構成できます。

RSA暗号は素因数分解の計算困難性に基づいた公開鍵暗号で、世界的に利用されています。

公開鍵暗号が存在することで、インターネット上で初対面の相手とも安全に暗号化された通信が可能となります。

この他にも、離散対数問題の計算困難性に基づいたDiffie-Hellman鍵交換、楕円曲線上の離散対数問題の計算困難性に基づいた楕円曲線暗号など、NP困難を基として様々な公開鍵暗号が構成されています。

この情報化社会はNP困難によって守られていると言っても過言ではありません。

NPの危機

しかし、安心してはいけません。

量子コンピュータが実現されれば、素因数分解が多項式時間で完了するような量子アルゴリズムがすでに作られています。

このため、近い将来にRSA暗号は崩壊するかもしれないということが危惧されています。

また、RSA暗号の内、偶然にも性質が悪くなってしまった場合には容易に素因数分解されたり、複号できてしまったりすることもあります。

NP困難と適切に付き合うことで、セキュリティを上げる必要があります。

終わりに

以上、NPについてでした。情報科学科や情報工学科に進む人にとっては避けては通れないジャンルだと思います。

NPはP≠NP予想などに言われるように未解決問題が多くあり、NP問題の解を求めるアルゴリズムやヒューリスティックは現代でも盛んに研究されているジャンルです。

特にスーパーコンピュータの性能が上がり、気軽に利用できる昨今では、計算リソースで無理やり解くなどということもできるため、RSA暗号等がどれだけ安全でいられるかなども注目されるでしょう。

セキュリティを保つためにも、どこまで解かれてしまうかのラインを知ることは重要で、CTFでもRSA暗号を攻撃する問題が多数存在します。

この機会に是非NP問題に興味を持っていただければと思います。最適解が基本的に出ないので、いくら遊んでも終わりがありません。楽しいですよ(白目)。

明日はhihumiさんとCulMenさんの記事です。