現代暗号とP≠NP予想
この記事は？
現代暗号とP≠NP予想は切っても切り離せない関係にあります。それがどういうことなのか？を解説しようと思います。
RSA暗号やPythonなどがでてきますが、詳しくなくても読めると思います（たぶん）
P≠NP予想
P≠NP予想 はミレニアム懸賞問題のひとつで、重要な未解決問題です。以下のP問題とNP問題が果たして、
P(Polynomial Time)
ある判定問題がPに属するなら
- 多項式時間で解くことが出来る。
- 同値な定義として、決定性チューリングマシンで多項式時間で解くことが出来る。
NP(Non-Deterministic Polynomial Time)
ある判定問題がNPに属するなら
- 問題に対する証拠wが与えられたとき、その証拠wが本当に正しいかどうかを多項式時間で判定できる。
- 同値な定義として、非決定性チューリングマシンで多項式時間で解くことが出来る。
多項式時間とは最悪でも
NP問題の中にはNP完全問題という問題があります。NP完全問題は、NP問題から多項式時間で変換することができる最も難しい問題です。NP完全問題が解かれることは他のNP問題が解かれることを意味します。
このNP完全問題を効率的に解くアルゴリズムはありそうにもない、ということでP≠NPなのではないかと予想されています。しかし、それが予想にとどまっているのが現状です。
P=NPだと暗号が破られる
さて、もし
まずNP問題はこんな定義でした。
- 問題に対する証拠wが与えられたとき、その証拠wが本当に正しいかどうかを多項式時間で判定できる。
これを暗号に読み替えるとこうなります。
- ある「暗号文
c m sk sk
そう、暗号関数は秘密鍵
この証拠を知っているかどうかで計算ができるかどうかが変わるという非対称性を利用したのが現代暗号です。[1]
もしも
この「信じられている」のことを暗号では仮定といいます。例えば、素因数分解が難しいとか離散対数が難しいなどの仮定です。
決定性と非決定性
NP問題にはもう一つ、「非決定性チューリングマシンで多項式時間で解くことが出来る」 という定義があります。これについて説明しつつ、P≠NP問題について深堀りします。
決定性チューリングマシンと非決定性チューリングマシンはある関数が解けるアルゴリズムが存在するかをモデル化したものです。これをより身近にした、決定性アルゴリズムと非決定性アルゴリズムについて説明しましょう。決定性アルゴリズムで解ければその問題はP、非決定性アルゴリズムで解ければNPです。これら２つの違いは、毎回の動作が予測できるかどうかです。
具体例
例えば、ある数字をRSA暗号で暗号化しました。この数字を知るためには
ここで、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暗号の鍵が
しかしprivate_key（秘密鍵、証拠）を知っていれば、
しかし、このようなアルゴリズム（？）ならどうでしょうか？
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問の選択式テストで全問正解するは答えを知っていれば答え通りにマークするだけですが、ヤマカンでは
多項式時間決定性アルゴリズムは存在するのか？
ではRSAを効率的に解けるような決定性アルゴリズムを考えるわけですが、これは存在しないと信じられています。これが
def solve(cipher_text,plain_text):
plain_text=sub_routine(cipher_text,plain_text)
return plain_text
暗号関数を破ることがP問題であれば、すべての計算量仮定に基づいた暗号に対して効率的に破る決定性アルゴリズムが存在することになります。決定性アルゴリズムなので、誰がやっても多項式時間で解けてしまうわけです。誰がやっても暗号を解読できてしまうのは、もはや暗号が機能していないのと同じになります。
- Note
ちなみに非決定性アルゴリズム（非決定性チューリングマシン）と等価な問題を解く、決定性アルゴリズム（決定性チューリングマシン）が構成できることが知られています。しかし、この決定性アルゴリズムは極めて効率が悪い可能性があります。
これは、計算可能性の文脈では同じ能力を持つが計算複雑性の文脈では同じ能力を持たないということです。
まとめ
暗号技術の仮定は
飲み込みが違ってくるのではないかと思います。私は計算複雑性の話が身近ではありませんでしたが、競技プログラミングを通して身近に感じるようになりました。
次は全てのNPとゼロ知識証明の関係について書こうと思っています！
おわり
Discussion