現代暗号とP≠NP予想

公開:2020/09/28
更新:2020/09/30
4 min読了の目安(約3600字TECH技術記事
Likes12

この記事は?

現代暗号とP≠NP予想は切っても切り離せない関係にあります。それがどういうことなのか?を解説しようと思います。
RSA暗号やPythonなどがでてきますが、詳しくなくても読めると思います(たぶん)

P≠NP予想

P≠NP予想 はミレニアム懸賞問題のひとつで、重要な未解決問題です。以下のP問題とNP問題が果たして、P=NPP=NPなのかPNPP\neq NPなのかを問う問題です。

P(Polynomial Time)

ある判定問題がPに属するなら

  • 多項式時間で解くことが出来る。
  • 同値な定義として、決定性チューリングマシンで多項式時間で解くことが出来る。

NP(Non-Deterministic Polynomial Time)

ある判定問題がNPに属するなら

  • 問題に対する証拠wが与えられたとき、その証拠wが本当に正しいかどうかを多項式時間で判定できる。
  • 同値な定義として、非決定性チューリングマシンで多項式時間で解くことが出来る。

多項式時間とは最悪でもO(nx)O(n^x)の計算量オーダとなることです。それに対し、指数時間であればO(2n)O(2^n)のような指数関数の計算量オーダになります。

NP問題の中にはNP完全問題という問題があります。NP完全問題は、NP問題から多項式時間で変換することができる最も難しい問題です。NP完全問題が解かれることは他のNP問題が解かれることを意味します。

このNP完全問題を効率的に解くアルゴリズムはありそうにもない、ということでP≠NPなのではないかと予想されています。しかし、それが予想にとどまっているのが現状です。

P=NPだと暗号が破られる

さて、もしPNPP\neq NP予想に反してP=NPP=NPだと現代暗号は解読されてしまいます。これがどういうことなのか説明します。

まずNP問題はこんな定義でした。

  • 問題に対する証拠wが与えられたとき、その証拠wが本当に正しいかどうかを多項式時間で判定できる。

これを暗号に読み替えるとこうなります。

  • ある「暗号文ccの平文はmmである」という問題と秘密鍵skskが与えられたとき、そのskskが正しいことを多項式時間で判定出来る。

そう、暗号関数は秘密鍵skskを証拠としたNP問題であり、多項式時間では解けません(正確には解けないと信じられている)。秘密鍵があれば効率的に平文を復号でき、秘密鍵がなければ復号は困難です。

この証拠を知っているかどうかで計算ができるかどうかが変わるという非対称性を利用したのが現代暗号です。[1]

もしもP=NPP=NPならば暗号関数はP問題でもあるということになります。つまり多項式時間で復号するようなアルゴリズムが存在することになり安全性の保障が出来なくなります。

この「信じられている」のことを暗号では仮定といいます。例えば、素因数分解が難しいとか離散対数が難しいなどの仮定です。

決定性と非決定性

NP問題にはもう一つ、「非決定性チューリングマシンで多項式時間で解くことが出来る」 という定義があります。これについて説明しつつ、P≠NP問題について深堀りします。

決定性チューリングマシンと非決定性チューリングマシンはある関数が解けるアルゴリズムが存在するかをモデル化したものです。これをより身近にした、決定性アルゴリズムと非決定性アルゴリズムについて説明しましょう。決定性アルゴリズムで解ければその問題はP、非決定性アルゴリズムで解ければNPです。これら2つの違いは、毎回の動作が予測できるかどうかです。

具体例

例えば、ある数字をRSA暗号で暗号化しました。この数字を知るためには21282^{128}のパターンある秘密鍵が必要です。この秘密鍵を特定する愚直な方法として以下のようなプログラムが考えられます。
ここで、decをRSAの復号関数、isPlain()を正しい平文かどうか判定する関数とします。

def solve(cipher_text,plain_text,private_key):
	while isPlain(dec(cipher_text,private_key)):
		private_key+=1
	return plain_text

全探索です。このアルゴリズムは同じ引数が与えられたなら、いつでも同じ動作をすることでしょう[2]決定性アルゴリズムといえます。

さて、これはRSA暗号を理論上は解いてくれる決定性アルゴリズムですが、RSA暗号の鍵が21282^{128}パターンあるので、この全探索は多項式時間では終わらないと言えます。
しかしprivate_key(秘密鍵、証拠)を知っていれば、21282^{128}を一回もループせずにこのアルゴリズムは終了します。証拠があれば多項式時間で解けるというNP問題の定義に一致しています。

しかし、このようなアルゴリズム(?)ならどうでしょうか?

def solve(cipher_text,plain_text,private_key):
	private_key=int(input())
	while isPlain(dec(cipher_text,private_key)):
		private_key+=1
	return plain_text

関数に加えてユーザが入力するinput()があるので、このアルゴリズムの動作は引数が同じでも毎回異なる可能性があり、予想できません。ユーザーの入力によっては、一発で終わるかもしれないし、多項式時間ではとけないかもしれません。

つまり非決定的といえます。ここでもし、ユーザーがinput()として正しい秘密鍵を入力すれば復号に多項式時間で成功するでしょう。答えを知っていること=非決定動作ということです。

つまり、

  • ユーザーが秘密鍵を知っていれば、効率的に解ける=特定の動作をすれば、効率的に解ける

  • 証拠を知っていれば、効率的に解ける=非決定動作を許せば、効率的に解ける

ということになります。二択100問の選択式テストで全問正解するは答えを知っていれば答え通りにマークするだけですが、ヤマカンでは21002^{100}パターンの回答を試す必要があるのと一緒です。

多項式時間決定性アルゴリズムは存在するのか?

ではRSAを効率的に解けるような決定性アルゴリズムを考えるわけですが、これは存在しないと信じられています。これがPNPP\neq NP予想です。

P=NPP=NPだった場合、NP問題は全てP問題、つまり証拠w(秘密鍵)なし多項式時間で計算ができる決定性アルゴリズムが存在することになります。そのアルゴリズムをサブルーチンとして用いた以下のプログラムは多項式時間で動作し、RSA暗号を破ることになります。

def solve(cipher_text,plain_text):
	plain_text=sub_routine(cipher_text,plain_text)
	return plain_text

暗号関数を破ることがP問題であれば、すべての計算量仮定に基づいた暗号に対して効率的に破る決定性アルゴリズムが存在することになります。決定性アルゴリズムなので、誰がやっても多項式時間で解けてしまうわけです。誰がやっても暗号を解読できてしまうのは、もはや暗号が機能していないのと同じになります。

  • Note
    ちなみに非決定性アルゴリズム(非決定性チューリングマシン)と等価な問題を解く、決定性アルゴリズム(決定性チューリングマシン)が構成できることが知られています。しかし、この決定性アルゴリズムは極めて効率が悪い可能性があります。
    これは、計算可能性の文脈では同じ能力を持つが計算複雑性の文脈では同じ能力を持たないということです。

まとめ

PNPP=NPだとNP問題である暗号関数がP問題になってしまうので多項式時間で解かれてしまうということです!

暗号技術の仮定はPNPP≠NP予想に基づいているため、これを理解しているかどうかで暗号の安全性理論の
飲み込みが違ってくるのではないかと思います。私は計算複雑性の話が身近ではありませんでしたが、競技プログラミングを通して身近に感じるようになりました。

次は全てのNPとゼロ知識証明の関係について書こうと思っています!

おわり

脚注
  1. このことを一方向性とも言います。 ↩︎

  2. 関数型言語だと参照透過性とか言いますよね。 ↩︎