アメリカ国立標準技術研究所NISTで2016年から進行していたPQC, Post-Quantum Cryptography 耐量子暗号プロジェクトが2022年7月５日、大きな山場を迎えました。スーパーコンピューターを使っても１億年以上解読するのに時間が掛かる楕円曲線暗号でも、量子コンピューターが実用化すれば安全ではないと懸念されていたのですが、量子コンピューターが実用化しても、それでも安全な暗号方式を策定しようというプロジェクトです。
量子コンピューターの開発と、暗号強度の向上が競争しているイメージです。実際に動かすという意味での数千ビットの誤り耐性量子コンピューターは実用化していませんが、数学的な意味では量子コンピューターは完成しているので、つまりアーキテクチャーは完成しているので、実用化したらどうなる、ということは事前に分かるわけです。
それで耐量子公開鍵暗号の策定作業が進み、今回、最終候補が１つに絞られ発表されたのです。それがCRYSTALS-KYBERクリスタルキーバーです。今後２年かけて最終確認して正式に標準化される予定です。もう最終候補はひとつしかありませんので、事実上決まったのです。暗号の新時代がやって来ました！
CRYSTALS-KYBER
それはノイズが付加された多元連立方程式の求解困難性を根拠とする暗号方式ということです。鍵長は1024ビット以上が検討されているようです（ちなみにビットコインの鍵長は256ビット）。多元連立方程式は、デジタル計算なので整数の解となります。それは座標空間上に格子状に並んでいる整数点（ベクトル）を求めることになりますので、「格子暗号」と呼ばれています。ノイズの付加は、Oded Regev博士が提案したLWE問題 Learning With Errors問題と呼ばれています。中学生の時にやりましたね、連立方程式。それが、もう、100元とか、１千元とかの超多変数の連立方程式になってしまうのです。しかも消去法では解けないようにするために、誤差付きの式が沢山含まれているというのです！これは素因数分解とは関係なく、つまりショアのアルゴリズムが使えず、総当たりに近い方法で解を探すしかないんじゃないのか？というのがミソのようです。
※参考記事、システム制御情報学会６５巻２号より「量子コンピュータに耐性のある暗号技術と標準化の動向」
https://www.jstage.jst.go.jp/article/isciesci/65/2/65_60/_pdf
こちらの記事によるとCRYSTALS-KYBERの秘密鍵は1632バイトになっているそうです。整数長を64ビット（８バイト）とすると、なんと204元連立方程式っていうことになります。ビットコインの鍵長が32バイト（256ビット）ですから、1632バイトのCRYSTALS-KYBERは鍵長だけでも５１倍になっています。気が遠くなるほどの暗号強度ですね！
LWEチャレンジ
LWE問題の困難性を実証するために、2016年からLWEチャレンジというインターネット上のコンテストも続いています。どの程度のパラメータ（次元数、ノイズ量）のLWE問題が現代コンピューターで解けるのかを実証し続けています。そこから逆算して、未来のスパコンや未来の量子コンピューターでも解けないようなLWE問題の条件を定めようとしているのです。
こちらのサイトを見ると、50元連立方程式でもノイズ量によっては最新コンピューターでも計算困難な状態になることが分かります。これが、現在のビットコインの楕円曲線暗号と同じ256ビットや、それ以上の鍵長で実装されたらどれくらい難しい問題になるのか、これを何となく体感することが必要です。
ビットコインへの影響
今後、このnistの最終候補発表を受けて雑誌記事や書籍の出版も増えると思われますので、要チェックです。２年後、この新しい暗号の安全性が正式に認められた場合には、いや、認められる前であっても、この公開鍵暗号を取り入れる暗号資産が増えていくと思われます。そして勿論、ビットコインなど暗号資産の公開鍵にも使われることになるでしょう。耐量子アドレスの導入です。暗号資産の安全性が高まることになります。
現代の公開鍵暗号は、21世紀の我々にとって銀行の金庫みたいなものです。自分のお金を預ける金庫がどれくらい強固なものか、学ぶ必要があるのです。20世紀までは「どの通貨で資産を保有するか」や、「どこの銀行にお金を預けるか」を考えてきましたが、21世紀には、「どの暗号の通貨を持つか」と考えなければならないのです。そうしないと、資産を維持することはできない時代なのです。
※参考記事
※参考書籍
現代暗号技術入門（CRYSTALS-KYBERの解説もあり）
暗号と量子コンピュータ
コメントを残す