次世代公開鍵暗号

公開:2020/09/26
更新:2020/09/27
2 min読了の目安(約1400字IDEAアイデア記事

次世代暗号の世界標準を決定する第4ラウンドが始まりました。

https://www.nist.gov/news-events/news/2020/07/nists-post-quantum-cryptography-program-enters-selection-round

効率性ではほかの候補より劣るものの、絶大な安全性を持つのがMcEliece暗号です。(実装は簡単な方だと思うし、巨大整数を使わず解読するのはものすごく難しい)
効率性で特に問題なのが、この暗号の公開鍵が800メガバイト以上あるということです。
到底ICカードには使えません。
プロセッサのキャッシュにも入りません。ただ演算装置にするときは比較的単純な回路になるだろうと思われます。
この暗号方式は誤り訂正符号に基づく暗号の代表として選抜されたようです。
もしこの方式が世界標準になれば、ほぼ強制的にRSAの代わりとして実装されることになるので、このような大容量メモリが必要な暗号の出番はあまり現実的じゃないのではと思います。

鍵の大きさに関する私のアイデアとしては、バイナリ符号を使った場合、公開鍵に偽のデータ列を混ぜることで、どの列に正しい公開鍵があるかを知らない限り効率的に復号できないだろうという感じです。
あるいはこの方法をバイト誤り訂正符号に使っうほうが適しているかもしれません。
どの列が正しい鍵なのかを識別できなければ、公開鍵のサイズをかなり抑えられるのではないかと思われるのですが、今のところなんの根拠もないアイデアです。
任意の列を取り出してInformation Set Decoding攻撃を使えば無理やり復号できるかもしれないので、符号長は少なくとも2000ビット(鍵サイズは2048*256ビット)は必要なはずですが、試せば解ることをやらないのが愚か('A`)。
もしこの推測が正しければ、符号長や次元を1ビット増やすとどのくらい攻撃に必要な計算量が増えるかを評価すると最適なパラメータがわかると思います。
提案されている方式のパラメータは符号長で言えば最大で8192ビットになっています。

私が学生時代から注目していたこの暗号方式が、最終選考にまで残ったのはうれしいです。
それは最終的に世界標準にならなくても、バックアップ用の選択肢として実装されるかもしれないことを意味しているからです。
その点、他の候補はまだ作られて日も浅く、どのような安全性を持つのかはいまだ未確定です。
例えば、鳴り物入りでブームになった超楕円曲線暗号のように、集中的な研究によって次々と破られた暗号もあります。
なので、コロナの影響もあり、合計20の最終候補(公開鍵暗号については4候補。ベスト4入り)の中から今後2年間をかけて公開鍵暗号、電子署名、鍵交換などそれぞれの世界標準が決められる予定だそうです。

https://csrc.nist.gov/Projects/post-quantum-cryptography/round-3-submissions

実は私、学生時代からマックエリース暗号の関心を持ち続けていて、かなり詳しい方です。
実際にプログラミングしてみました。まだ暗号まで作ってませんが復号関数は出来上がっています。
また機会があったら暗号まで完成させるつもりです。
気になったら以下のリンクにソースがあります。

https://github.com/anang0g0/GoppaDecorder