McEliece 暗号システム

暗号学において、マケリース暗号システムは、1978年にロバート・マケリースによって開発された非対称暗号化アルゴリズムです。^{[1]これは、暗号化プロセスで}ランダム化を使用する最初の方式でした。このアルゴリズムは、暗号コミュニティではあまり受け入れられませんでしたが、ショアのアルゴリズムを使用した攻撃や、より一般的にはフーリエサンプリングを使用した剰余類状態の測定に対する耐性があるため、「ポスト量子暗号」の候補となっています。^[2]

このアルゴリズムは、一般線形コード（ NP困難であることが知られている^{[3] ）の}復号の難しさに基づいています。秘密鍵の記述には、効率的な復号アルゴリズムが知られており、エラーを訂正できるエラー訂正コードが選択されます。元のアルゴリズムは、バイナリゴッパコード（特性2の有限体上の種数0曲線の代数幾何学コードの部分体コード）を使用します。これらのコードは、パターソンによるアルゴリズムのおかげで効率的に復号できます。^[4]公開鍵は、選択されたコードを一般線形コードとして偽装することで、秘密鍵から導出されます。このため、コードの生成行列は、ランダムに選択された2つの可逆行列とによって摂動されます（以下を参照）。 ${\displaystyle t}$ ${\displaystyle G}$${\displaystyle S}$${\displaystyle P}$

この暗号システムには、異なるタイプのコードを使用するバリエーションが存在します。それらのほとんどは安全性が低いことが証明されており、構造的デコードによって解読されました。

ゴッパコードを使用したマケリースは、これまで暗号解読に抵抗してきました。最も効果的な攻撃として知られているのは、情報セット復号アルゴリズムです。2008年の論文では、攻撃と修正の両方について説明しています。^{[5]別の論文では、}量子コンピューティングでは、情報セット復号の改善により、キーサイズを4倍に増やす必要があることが示されています。 ^[6]

McEliece暗号システムは、例えばRSAに比べていくつかの利点があります。暗号化と復号化が高速です。^[7]長い間、McElieceは署名の生成には使用できないと考えられていました。しかし、署名方式は、McEliece方式の双対型であるNiederreiter方式に基づいて構築できます。McElieceの主な欠点の1つは、秘密鍵と公開鍵の行列が大きいことです。標準的なパラメータ選択では、公開鍵の長さは512キロビットです。

McEliece は、公開鍵と秘密鍵を生成する確率的鍵生成アルゴリズム、確率的暗号化アルゴリズム、および決定論的復号化アルゴリズムの 3 つのアルゴリズムで構成されています。

McEliece 展開内のすべてのユーザーは、一連の共通セキュリティ パラメータを共有します。 ${\displaystyle n,k,t}$

原理は、アリスが、効率的な復号アルゴリズムを知っているコード族から線形コードを選択し、その知識を公開するが、復号アルゴリズムは秘密にしておくというものです。このような復号アルゴリズムでは、任意の生成行列を知っているという意味で を知っているだけでなく、選択したコード族で指定するときに使用するパラメータを知っている必要があります。たとえば、バイナリ Goppa コードの場合、この情報は Goppa 多項式とコード ロケータになります。したがって、アリスは の適切に難読化された生成行列を公開できます。 ${\displaystyle C}$${\displaystyle C}$${\displaystyle C}$${\displaystyle C}$${\displaystyle C}$

具体的には、手順は以下のとおりです。

1. アリスは、バイナリ ゴッパ コードなどの大規模なコード ファミリから、(効率的に) エラーを訂正できるバイナリ-線形コードを選択します。この選択により、効率的なデコード アルゴリズム が生成されるはずです。を の任意の生成行列とします。任意の線形コードには多くの生成行列がありますが、このコード ファミリには自然な選択がしばしばあります。これを知ると暴露されるため、秘密にしておく必要があります。${\displaystyle (n,k)}$${\displaystyle C}$${\displaystyle t}$${\displaystyle A}$${\displaystyle G}$${\displaystyle C}$${\displaystyle A}$
2. アリスはランダムな2進非特異行列を選択します。${\displaystyle k\times k}$ ${\displaystyle S}$
3. アリスはランダムな順列行列を選択します。${\displaystyle n\times n}$ ${\displaystyle P}$
4. アリスは行列を計算します。${\displaystyle k\times n}$${\displaystyle {\hat {G}}=SGP}$
5. アリスの公開鍵は、秘密鍵は です。はを選択するために使用されるパラメータとしてエンコードされ、保存される可能性があることに注意してください。${\displaystyle ({\hat {G}},t)}$${\displaystyle (S,P,A)}$${\displaystyle A}$${\displaystyle C}$

ボブが公開鍵が であるアリスにメッセージm を送信したいとします。 ${\displaystyle ({\hat {G}},t)}$

1. ボブはメッセージを長さ のバイナリ文字列としてエンコードします。${\displaystyle m}$${\displaystyle k}$
2. ボブはベクトルを計算します。${\displaystyle c=m{\hat {G}}}$
3. ボブは、ちょうど1を含むランダムなビットベクトル（長さと重みのベクトル）を生成する^[1]${\displaystyle n}$${\displaystyle z}$${\displaystyle t}$${\displaystyle n}$${\displaystyle t}$
4. ボブは暗号文を次のように計算します。${\displaystyle c=c^{\prime }+z}$

を受信すると、アリスは次の手順を実行してメッセージを復号化します。 ${\displaystyle c}$

1. アリスは（すなわち）の逆関数を計算します。${\displaystyle P}$${\displaystyle P^{-1}}$
2. アリスは を計算します。${\displaystyle {\hat {c}}=cP^{-1}}$
3. アリスはデコードアルゴリズムを使用してにデコードします。${\displaystyle A}$${\displaystyle {\hat {c}}}$${\displaystyle {\hat {m}}}$
4. アリスは を計算します。${\displaystyle m={\hat {m}}S^{-1}}$

、およびは順列行列であるため、重み を持つことに注意してください。 ${\displaystyle {\hat {c}}=cP^{-1}=m{\hat {G}}P^{-1}+zP^{-1}=mSG+zP^{-1}}$${\displaystyle P}$${\displaystyle zP^{-1}}$${\displaystyle t}$

Goppa コードは最大 個のエラーを訂正でき、ワードはから最大で 個の距離にあります。したがって、正しいコードワードが得られます。 ${\displaystyle G}$${\displaystyle t}$${\displaystyle mSG}$${\displaystyle t}$${\displaystyle cP^{-1}}$${\displaystyle {\hat {m}}=mS}$

の逆数を掛けると となり、これがプレーンテキスト メッセージになります。 ${\displaystyle S}$${\displaystyle m={\hat {m}}S^{-1}=mSS^{-1}}$

行列 には自由な選択があるため、最後の列が単位行列 に対応するように「体系的な形式」で表現するのが一般的です。これにより、鍵のサイズは に縮小されます。^{[8] [9]} McEliece は当初、 のセキュリティパラメータサイズを提案し、^{[1]公開鍵のサイズは}524 × (1024 − 524) =になりました。${\displaystyle S}$${\displaystyle {\hat {G}}}$${\displaystyle k}$${\displaystyle {\hat {G}}=({\tilde {G}}|I)}$${\displaystyle (nk)\times k}$${\displaystyle n=1024,k=524,t=50}$262,000 ビット。最近の分析では、標準的な代数復号法を使用する場合、または80ビットのセキュリティを実現するにはパラメータサイズが262,000ビットであることが示唆されており、公開鍵のサイズは${\displaystyle n=2048,k=1751,t=27}$${\displaystyle n=1632,k=1269,t=34}$520 047とそれぞれ460 647 ビットである。^[5]量子コンピュータに対する耐性のために、ゴッパ符号のサイズが提案され、公開鍵のサイズは${\displaystyle n=6960,k=5413,t=119}$8 373 911 ビット。^[10] NISTポスト量子標準化ラウンド3の提出では、パラメータセット6688128、6960119、8192128に対して最高レベルのセキュリティであるレベル5が与えられている。パラメータはそれぞれ、、である。 ${\displaystyle n=6688,k=128,t=13}$${\displaystyle n=6960,k=119,t=13}$${\displaystyle n=8192,k=128,t=13}$

攻撃は、公開鍵は知っているが秘密鍵は知らない攻撃者が、傍受した暗号文から平文を推測することで行われます。このような試みは実行不可能であるはずです。 ${\displaystyle ({\hat {G}},t)}$${\displaystyle y\in \mathbb {F} _{2}^{n}}$

McEliece の攻撃には主に 2 つの種類があります。

攻撃者は、組み合わせ的にエラーを訂正できるコードの生成行列を知っています。攻撃者は、 が実際には特定のファミリーから選択された構造化コードの難読化であるという事実を無視し、代わりに任意の線形コードでデコードするためのアルゴリズムを使用する可能性があります。コードの各コードワードを調べる、シンドロームデコード、情報セットデコードなど、いくつかのそのようなアルゴリズムが存在します。 ${\displaystyle {\hat {G}}}$${\displaystyle (n,k)}$${\displaystyle {\hat {C}}}$${\displaystyle t}$${\displaystyle {\hat {C}}}$

しかし、一般的な線形符号の復号はNP困難であることが知られており^[3]、上記の方法はすべて指数関数的な実行時間を要する。

2008年、Bernstein、Lange、Peters ^{[5]は、Stern [11]}の情報セット復号法を使用して、オリジナルのMcEliece暗号システムに対する実用的な攻撃を説明しました。McElieceによって最初に提案されたパラメータを使用すると、攻撃は2 ^60.55ビット操作 で実行できます。攻撃は驚くほど並列であるため（ノード間の通信は不要）、小規模なコンピュータクラスターで数日で実行できます。

攻撃者は代わりに の「構造」を復元しようと試み、それによって効率的なデコード アルゴリズムまたは十分に強力で効率的な別のデコード アルゴリズムを復元する可能性があります。 ${\displaystyle C}$${\displaystyle A}$

選択されるコード ファミリによって、攻撃者がこれを実行できるかどうかが完全に決まります。McEliece には多くのコード ファミリが提案されていますが、そのほとんどは、リード ソロモン コードなどの効率的なデコード アルゴリズムを復元する攻撃が見つかったという意味で完全に「破られて」います。 ${\displaystyle C}$

当初提案されたバイナリ ゴッパ コードは、構造的攻撃を考案する試みにほとんど抵抗してきた数少ないコード ファミリの 1 つです。

このアルゴリズムの変種をNTS-KEM ^{[12]と組み合わせたものが、} NISTの 量子暗号コンペティションの第3ラウンドで採用され、選ばれた。^[13]

• Alfred J. Menezes、Scott A. Vanstone、AJ Menezes、Paul C. van Oorschot (1996)。「第 8 章: 公開鍵暗号化」。応用暗号ハンドブック。CRC Press。ISBN 978-0-8493-8523-0。
• Rahmschmid, Claudia; Adams, David (2023)。McEliece Messaging: Smoke Crypto Chat - 安定したプロトタイプとして世界初公開されたモバイル McEliece-Messenger。TK Info Portal の記事。
• 「量子コンピュータ? 未来のインターネット セキュリティ コードが解読される」。サイエンス デイリー。アイントホーフェン工科大学。2008 年 11 月 1 日。
• 「クラシック・マケリース」。（NIST耐量子暗号標準化プロジェクトへの提出）