McEliece and Rust: Edging Slowly To A NIST Standard for PQC

McEliece and Rust: Edging Slowly To A NIST Standard for PQC

We live in a world that is dominated by large (and faceless) corporations, but it is individuals who have often built our information world. One of those was Robert J. McEliece, and who passed away in May 2019 at the age of 76. While working on a range of space-related projects, he contributed in many areas including information transmission and storage. Robert eventually was awarded the Claude E. Shannon Award for his work, and gave many memorable talks:

and:

His best know work is around error-correcting codes, including within convolution codes, and now his work is causing great attention in creating an encryption system that would be robust against a quantum computer.

His work

Many of our public key methods are based on discrete logarithms and which build on the theories created by John Napier. Bitcoin, Tor, smart cards, Wif-fi, and many other applications use discrete logarithms. But these methods, and other public-key methods, are at risk from quantum computers. One contender is the McEliece Cryptography method.

In a lesson for any modern researcher, in just two pages, Robert McEliece, in 1978, outlined a public key encryption method based on Algebraic Coding — now known as the McEliece Cryptography method [paper][1]. It is an asymmetric encryption method (with a public key and a private key), and, at the time, looked to be a serious contender for a trapdoor method. Unfortunately, RSA became the King of the Hill, and the McEliece method was pushed to the end of the queue for designers.

It has basically drifted for nearly 40 years. But, as an era of quantum computers is dawning, it is now being reconsidered, as it is seen to be immune to attacks using Shor’s algorithm [here].

NIST has now started to move on to quantum robust methods with a paper outlining the requirement for new cryptography methods, as a large-scale quantum computer will break most of the currently available public-key systems, including RSA and discrete logarithm methods. Overall public key encryption is most often used to protect secret keys used in symmetric encryption and to prove identity. A large-scale breach of a public key would lead to a complete lack of trust on the Internet for the hacked entity.

The main contenders for quantum robust methods are:

• Lattice-based cryptography — This classification shows great potential and is leading to new cryptography, such as for fully homomorphic encryption [here] and code obfuscation. An example is given in the following section.
• Code-based cryptography — This method was created in 1978 with the McEliece cryptosystem but has barely been used in real applications. The McEliece method uses linear codes that are used in error-correcting codes, and involves matrix-vector multiplication. An example of a linear code is Hamming code [here]
• Multivariate polynomial cryptography — These focus on the difficulty of solving systems of multivariate polynomials over finite fields. Unfortunately, many of the methods that have been proposed have already been broken.
• Hash-based signatures — This would involve creating digital signatures using hashing methods. The drawback is that a signer needs to keep a track of all of the messages that have been signed and that there is a limit to the number of signatures that can be produced.

The McEliece method

The McEliece method uses code-based cryptography. Its foundation is based on the difficulty in decoding a general linear code and is generally faster than RSA for encryption and decryption. Within it, we have a probabilistic key generation method, which is then used to produce the public and the private key. The keys are generated with the parameters of n, k and T.

The keys are generated with the parameters of n, k and t. With this, we create an [n,k] matrix of codes, and which is able to correct t errors. In his paper, McEliece defines n=1024, k=524, t=50, and which gives a public key size of 524x(1024–524) = 262,000 bits. In the example above we use k=1608, N=2048 and T=40, which gives a public key size of 1608x(2048–40) — 3,228,864 bits. For quantum robustness it is recommended that N is 6960, k is 5,412 and t is 119 (giving a large key size of 8,373,911 bits.

The following is the derived key size and cipher text (in bytes) of each of the core methods [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

The following defines the key sizes for Kyber, SABER, NTRU and McEliece:

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

Code

First, we create the project with:

cargo new mce

We then go into the mce folder and add the following to the cargo.toml file:

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

The code is then [here]:

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()));

}

Finally we simply build with:

cargo build

A sample run is [here]:

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

We can see that the shared key for Bob and Alice is 32 bytes long (256 bits). The public key is 261,120 bytes long, and the secret key is 6,492 bytes. The cipher text is 96 bytes long.

McEliece performance

You will find the code is fairly slow, and can take a few seconds to create the shared key. This is because McEliece is much slower than Kyber for key generation [here]:

As we see, McEliece is 11,490 times slower for key generation as opposed to Kyber. But the encapsulation and decapsulation processes perform better, with a 1.9 times slower performance for encapsulation, and 9.7 times slower for decapsulation.

Conclusions

Kyber has been defined as the first method to be defined as a PQC Key Exchange and Public Key Encryption method. Overall, it is based on lattice methods. These are relatively fast for key generation, encryption and decryption, and with relatively small key sizes. NIST, though, has a worry that we will become too dependent on lattice methods, and so are looking for other methods. These include McEliece, BIKE, and HQC.

You can find out more here:

https://asecuritysite.com/pqc/kem

And some cracking:

References

[1] McEliece, R. J. (1978). A public-key cryptosystem based on algebraic. Coding Thv, 4244, 114–116.