こんにちは、Habr。最近、NISTはそのウェブサイトでポスト量子暗号の標準化の第3フェーズの開始を発表しました。デジタル署名の3つの候補と非対称暗号化の4つの候補が第3段階に渡されました。8つの代替候補も提示されました。Khabrovitesはこのイベントに興味があるだろうと思いました。カットの下の詳細。
ちょっとした歴史
量子コンピューティングのアイデアは、複雑な量子機械システムをシミュレートするために1980年代初頭に最初に提案されました。量子コンピューティングは、数値の因数分解や楕円曲線上の点のグループへの離散対数の取得など、他の問題に対して大幅な高速化を提供できることがすぐに判明しました。
一般的な標準化されたシステムのセキュリティはこれらの問題を解決する複雑さに依存するため、これは暗号化にとって重大な問題になっています。
それにもかかわらず、かなり長い間、量子コンピューティングは、技術的に実装することができなかった美しい抽象化のままでした。しかし最近、量子コンピューターの構築の実現可能性が再検討され、これによりNISTは2016年に新しいポスト量子標準を作成するためのオープンコンペティションを開始するようになりました。より具体的には、NISTは、公開鍵暗号化とデジタル署名の新しい標準の作成に関心を持っています。
世界中から69チームがコンテストへの参加を申請しました。このトピックは広く取り上げられ、Habréへの投稿もありました。提案されたスキームのうち、第2段階に合格したのは26のみでしたが、2020年7月22日に、第2段階のファイナリストが発表されました。非対称暗号化の候補は4つ、デジタル署名の候補は3つだけです。
第3段階に合格した候補者
したがって、新しいポストクォンタムデジタル署名標準の候補は次のとおりです。
- CRYSTALS-DILITHIUM-格子暗号の代表。これは、中断のあるフィアット-シャミール回路に基づいています。暗号分析は、Module-LWEおよびModule-SISの問題を解決することになります。パフォーマンスが高く、リソースの少ないデバイスに効果的に実装できます。NISTは、セキュリティレベル5のシステム全体のパラメータのセットを追加するように作成者に依頼しました。
- FALCON — . GPV. SIS NTRU-. . , , .
- Rainbow — . UOV. . - , .
NIST CRYSTALS-DILITHIUM FALCON . , . Rainbow.
:
- Classic McEliece — . 1979 . , . - , Rainbow .
- CRYSTALS-KYBER — . Module-LWE. -. , NIST , Module-LWE — .
- NTRU — . NTRUEncryt, 20 . NTRU, Module-LWE ( ) , .
- SABER — . MLWR (Module-LWE,
). -, CRYSTALS-KYBER.
, — . NIST , (CRYSTALS-KYBER, NTRU, SABER) .
NIST 8 , , .
:
- SPHINCS+ Picnic — . SPHINCS+ -, Picnic NIZK . . , .
- GeMSS — Rainbow, HFE, UOV. . Rainbow.
:
- BIKE — . .
- FrodoKEM — . LWE, Module-LWE ( ). \.
- HQC — . . \.
- NTRU Prime — . .
- SIKE — ( ), . .
NISTは、過去4年間に、世界中から提案されたポスト量子回路を分析してきました。提案されたスキームの中で、支配的な位置は格子スキームによって占められています。しかし、（他の分野と同様に）より詳細な調査が必要です。NISTは、今後3年間で残りの候補者の詳細な分析を実施する予定です。
：それは、すでに世界では、格子のスキームが標準化されていることは注目に値する1、2を。したがって、おそらく、今後数年間で通常のRSAおよびECDSAに取って代わるのは、格子上の暗号化です。しかし同時に、他のソリューションは高度に専門化された分野で人気があります。