McEliece と Rust: PQC の NIST 標準へのゆっくりとしたエッジング

May 08 2023

私たちは大規模な (そして顔のない) 企業が支配する世界に住んでいますが、情報世界を構築しているのは個人です。そのうちの 1 人は Robert J.

UnsplashのNerene Groblerによる写真

私たちは大規模な (そして顔のない) 企業が支配する世界に住んでいますが、情報世界を構築しているのは個人です。その一人が、2019年5月に76歳で亡くなったロバート・J・マケリース氏でした。彼は宇宙関連のさまざまなプロジェクトに取り組みながら、情報の伝達や保管など多くの分野で貢献しました。ロバートは最終的に彼の業績に対してクロード E. シャノン賞を受賞し、多くの思い出に残る講演を行いました。

と：

彼の最もよく知られている仕事は、畳み込みコード内を含むエラー訂正コードに関するものであり、現在、彼の仕事は、量子コンピューターに対して堅牢な暗号化システムを作成する上で大きな注目を集めています.

彼の仕事

私たちの公開鍵方式の多くは離散対数に基づいており、John Napier によって作成された理論に基づいています。ビットコイン、Tor、スマートカード、Wif-fi、およびその他の多くのアプリケーションでは、離散対数が使用されます。しかし、これらの方法やその他の公開鍵の方法は、量子コンピューターによる危険にさらされています。候補の 1 つは McEliece 暗号法です。

1978 年、Robert McEliece は、現在の McEliece 暗号化法として知られている、代数符号化に基づく公開鍵暗号化法をわずか 2 ページで概説した、現代の研究者のための教訓です [論文][1 ]。これは非対称暗号化方式 (公開鍵と秘密鍵を使用) であり、当時はトラップドア方式の有力な候補であると考えられていました。残念なことに、RSA がキングオブザヒルになり、McEliece メソッドは設計者のキューの最後に追いやられました。

それは基本的に40年近く漂流しています。しかし、量子コンピューターの時代が始まろうとしており、Shor のアルゴリズム [こちら] を使用した攻撃に対して免疫があることが見られるため、現在再考されています。

大規模な量子コンピューターは、RSA や離散対数法など、現在利用可能な公開鍵システムのほとんどを破壊するため、NIST は現在、新しい暗号化方法の要件を概説する論文で、量子ロバストな方法に移行し始めています。全体的な公開鍵暗号化は、対称暗号化で使用される秘密鍵を保護し、身元を証明するために最もよく使用されます。公開鍵が大規模に侵害されると、ハッキングされたエンティティに対するインターネット上の信頼が完全に失われます。

量子ロバストな方法の主な候補は次のとおりです。

格子ベースの暗号化— この分類は大きな可能性を示しており、完全準同型暗号化 [こちら] やコード難読化などの新しい暗号化につながっています。次のセクションで例を示します。
コードベースの暗号化— この方式は 1978 年に McEliece 暗号システムで作成されましたが、実際のアプリケーションではほとんど使用されていません。McEliece 法は、エラー訂正コードで使用される線形コードを使用し、行列とベクトルの乗算を伴います。線形符号の例は、ハミング符号です [ここ]
多変量多項式暗号— これらは、有限体上で多変量多項式のシステムを解くことの難しさに焦点を当てています。残念ながら、提案された方法の多くはすでに破られています。
ハッシュベースの署名— これには、ハッシュ方式を使用してデジタル署名を作成することが含まれます。欠点は、署名者が署名されたすべてのメッセージを追跡する必要があることと、生成できる署名の数に制限があることです。

McEliece メソッドは、コードベースの暗号化を使用します。その基礎は、一般的な線形コードのデコードの難しさに基づいており、暗号化と復号化では一般に RSA よりも高速です。その中には、確率的な鍵生成方法があり、公開鍵と秘密鍵を生成するために使用されます。鍵は、n、k、および T のパラメーターを使用して生成されます。

鍵は、n、k、および t のパラメーターを使用して生成されます。これにより、コードの [n,k] 行列を作成し、t 個のエラーを修正できます。McEliece は彼の論文で、n=1024、k=524、t=50 を定義しており、公開鍵のサイズは 524x(1024–524) = 262,000 ビットになります。上記の例では、k=1608、N=2048、T=40 を使用しています。これにより、公開鍵のサイズは 1608x(2048–40) — 3,228,864 ビットになります。量子ロバスト性のために、N を 6960、k を 5,412、t を 119 にすることをお勧めします (鍵のサイズは 8,373,911 ビットと大きくなります。

以下は、各コアメソッドの派生キーサイズと暗号テキスト (バイト単位) です [1]。

m    n      t   level | public key   secret key  ciphertext
--------------------------------------------------------------------------
mceliece348864  12  3,488    64	 1    |  261,120       6,492       128
mceliece460896  13  4,608    94	 3    |  524,160      13,608       188
mceliece6688128 13  6,688   128	 5    | 1,044,992     13,932       240
mceliece6960119 13  6,960   119  5    | 1,047,319     13,948       226
mceliece8192128 13  8,192   128  5    | 1,357,824     14,120       240

Type      Public key size (B)   Secret key size (B)  Ciphertext size (B)
------------------------------------------------------------------------
Kyber512              800              1,632                  768  Learning with errors (Lattice)
Kyber738            1,184              2,400                1,088  Learning with errors (Lattice)
Kyber1024           1,568              3,168                1,568  Learning with errors (Lattice)
LightSABER            672              1,568                  736  Learning with rounding (Lattice)
SABER                 992              2,304                1,088  Learning with rounding (Lattice)
FireSABER           1,312              3,040                1,472  Learning with rounding (Lattice)
McEliece348864    261,120              6,452                  128  Code based
McEliece460896    524,160             13,568                  188  Code based
McEliece6688128 1,044,992             13,892                  240  Code based
McEliece6960119 1,047,319             13,948                  226  Code based
McEliece8192128 1,357,824             14,120                  240  Code based
NTRUhps2048509        699                935                  699  Lattice
NTRUhps2048677        930              1,234                  930  Lattice
NTRUhps4096821      1,230              1,590                1,230  Lattice
SIKEp434              330                 44                  346  Isogeny
SIKEp503              378                 56                  402  Isogeny
SIKEp751              564                 80                  596  Isogeny
SIDH                  564                 48                  596  Isogeny

まず、以下を使用してプロジェクトを作成します。

cargo new mce

[package]
name = "mce"
version = "0.1.0"
edition = "2021"
[dependencies]
classic-mceliece-rust = "3.0"
rand = "^0.8.5"
hex="^0.4"

use classic_mceliece_rust::{keypair, encapsulate, decapsulate};
use classic_mceliece_rust::{CRYPTO_BYTES, CRYPTO_PUBLICKEYBYTES, CRYPTO_SECRETKEYBYTES};
use hex;
fn main() {
  let mut rng = rand::thread_rng();
  let mut public_key_buf = [0u8; CRYPTO_PUBLICKEYBYTES];
  let mut secret_key_buf = [0u8; CRYPTO_SECRETKEYBYTES];
  let (public_key, secret_key) = keypair(&mut public_key_buf, &mut secret_key_buf, &mut rng);
  println!("\nBob public key (showing first 32 out of {} bytes): {:.32}", CRYPTO_PUBLICKEYBYTES,hex::encode(public_key.as_array()));
  println!("\nBob secret key (showing first 32 out of {} bytes): {:.32}",CRYPTO_SECRETKEYBYTES,hex::encode(secret_key.as_array()));
 
  let mut shared_secret_bob_buf = [0u8; CRYPTO_BYTES];
  let (ciphertext, shared_secret_bob) = encapsulate(&public_key, &mut shared_secret_bob_buf, &mut rng);
  let mut shared_secret_alice_buf = [0u8; CRYPTO_BYTES];
  let shared_secret_alice = decapsulate(&ciphertext, &secret_key, &mut shared_secret_alice_buf);
  println!("\nCiphertext (Bob to Alice) (showing {} bytes): {}",ciphertext.as_array().len(),hex::encode(ciphertext.as_array()));
  println!("\nBob key:  (showing {} bytes) {}",shared_secret_bob.as_array().len(),hex::encode(shared_secret_bob.as_array()));
  println!("\nAlice key: (showing {} bytes) {}",shared_secret_alice.as_array().len(),hex::encode(shared_secret_alice.as_array()));

}

cargo build

Bob public key (showing first 32 out of 261120 bytes): 4b44ae97d30a04f2ade8334a4817b5cc
Bob secret key (showing first 32 out of 6492 bytes): 76ac75d052f030692d334d843bc29ee7

Ciphertext (Bob to Alice) (showing 96 bytes): f40bff3d7928cd70cd1cf8a04daaacbf67168585a79fc57a28fef71203771a2d572229f29079bf6fe1713e7b3444c9badaebd7a7277ef6c88db9f02a27b3ba98b6f82743b2ba4b47d781b5fc5b7657ee10ef5d30971c2f2d2a8395898e8c2fe0

Bob key:  (showing 32 bytes) bb2853e129206f1d9e2802a5e6bd93265545b0369eb91750d799b876d870ff30

Alice key: (showing 32 bytes) bb2853e129206f1d9e2802a5e6bd93265545b0369eb91750d799b876d870ff30

マケリースのパフォーマンス

コードはかなり遅く、共有キーの作成に数秒かかることがあります。これは、キー生成に関して McEliece が Kyber よりもはるかに遅いためです [こちら]:

ご覧のとおり、Kyber とは対照的に、McEliece はキー生成で 11,490 倍遅くなります。ただし、カプセル化とカプセル化解除プロセスのパフォーマンスは向上し、カプセル化では 1.9 倍、カプセル化解除では 9.7 倍遅くなります。

結論

Kyber は、PQC 鍵交換および公開鍵暗号方式として定義される最初の方式として定義されています。全体として、格子法に基づいています。これらは、鍵の生成、暗号化、および復号化が比較的高速で、鍵のサイズが比較的小さくなります。ただし、NIST は格子法に依存しすぎることを懸念しており、他の方法を探しています。これらには、McEliece、BIKE、および HQC が含まれます。

McEliece と Rust: PQC の NIST 標準へのゆっくりとしたエッジング

彼の仕事

マケリースのパフォーマンス

結論

参考文献