CRYSTALS-KYBERを学べ!


Screenshot of pq-crystals.org

アメリカ国立標準技術研究所NISTで2016年から進行していたPQC, Post-Quantum Cryptography 耐量子暗号プロジェクトが2022年7月5日、大きな山場を迎えました。

耐量子公開鍵暗号の最終候補が1つに絞られ発表されたのです。CRYSTALS-KYBERクリスタルキーバーです。今後2年かけて最終確認して正式に標準化される予定です。暗号の新時代がやって来ました!

Screenshot of www.nist.gov

CRYSTALS-KYBER

Screenshot of pq-crystals.org

それはノイズが付加された多元連立方程式の求解困難性を根拠とする暗号方式ということです。鍵長は1024ビットなどが検討されているようです。多元連立方程式は、デジタル計算なので整数の解となります。それは座標空間上に格子状に並んでいる整数点(ベクトル)を求めることになりますので、「格子暗号」と呼ばれています。ノイズの付加は、Oded Regev博士が提案したLWE問題 Learning With Errors問題と呼ばれています。中学生の時にやりましたね、連立方程式。それが、もう、1000元とか、1万元とかの超多変数の連立方程式になってしまうのです。しかも誤差付きの式が沢山含まれているというのです!

LWEチャレンジ

LWE問題の困難性を実証するために、2016年からLWEチャレンジというインターネット上のコンテストも続いています。どの程度のパラメータ(次元数、ノイズ量)のLWE問題が現代コンピューターで解けるのかを実証し続けています。そこから逆算して、未来のスパコンや未来の量子コンピューターでも解けないようなLWE問題の条件を定めようとしているのです。

Screenshot of www.latticechallenge.org

こちらのサイトを見ると、50元連立方程式でもノイズ量によっては最新コンピューターでも計算困難な状態になることが分かります。これが、現在のビットコインの楕円曲線暗号と同じ256ビットや、それ以上の鍵長で実装されたらどれくらい難しい問題になるのか、これを何となく体感することが必要です。

ビットコイン暗号資産への影響

今後、このnistの最終候補発表を受けて雑誌記事や書籍の出版も増えると思われますので、要チェックです。2年後、この新しい暗号の安全性が正式に認められた場合には、いや、認められる前であっても、この公開鍵暗号を取り入れる暗号資産が増えていくと思われます。そして勿論、ビットコインの公開鍵にも使われることになるでしょう。耐量子アドレスの導入です。

現代の公開鍵暗号は、21世紀の我々にとって銀行の金庫みたいなものです。自分のお金を預ける金庫がどれくらい強固なものか、学ぶ必要があるのです。20世紀までは「どこの銀行にお金を預けるか」考えてきましたが、21世紀には、「どの暗号の通貨を持つか」と考えなければならないのです。そうしないと、資産を維持することはできない時代なのです。

※参考書籍

現代暗号技術入門(CRYSTALS-KYBERの解説もあり)


コメントを残す

メールアドレスが公開されることはありません。