Assessing The PQC Also-rans … SIKE, BIKE and Classic McEliece

Well, I say “also-rans”, but they are not, as they actually progress to the next round. And so, last week, NIST announced the methods that…
Photo by Mathew Schwartz on Unsplash

Assessing The PQC Also-rans … SIKE, BIKE and Classic McEliece

And so, last week, NIST announced the methods that are going forward for standardization for PQC (Post Quantum Cryptography). This was Kyber for Public Key Encryption (PKE)/Key Exchange, and Dilithium, Falcon and SPHINCS+ for digital signatures. All but one of these methods is a lattice-based method.

The only non-lattice-based method is SPHINCS+, and which is a hash-based signature method. The reason for lattice methods dominating is that they have good performance levels, and have relatively small key sizes and ciphertext. But, what if we discovered a weakness in lattice methods, we could be in trouble if we just use them. Over the past few decades we have had ECC and RSA to provide alternatives, and each is based on a different trap door problem.

But, we forget that there is now a Round 4, and a few candidates progress into another set of assessments. This includes BIKE (a code-based method), and Classic McEliece (a code-based method) and SIKE (an isogeny-based method) moving forward into Round 4 for Public Key Encryption/Key Exchange. Overall, Kyber will sprint ahead, but let’s look at the other three that could join it as a PQC standard.

In the following table, I have run the methods on a Linux computer. We see that BIKE-L1 has a fairly good performance for key encapsulation (3.7 times slower than Kyber512), but not so good for key decapsulation (269 times slower than Kyber512). The key generation is reasonable too for its performance (24.2 times slower than Kyber512) [here]:

SIKE-p503 does not do as well as BIKE, with 285 times slower than Kyber for key encapsulation, 491 times slower for key generation, and 791 times slower for key encapsulation. It is much slower for key generation than BIKE [here]:

When it comes to Classic McEliece, the key generation phase is terrible for performance (with the best being 11,490 times slower than Kyber512). Once the key is created, the performance is actually fairly good with only 1.9 times slower than Kyber512 for key encapsulation, and 9.7 times slower than Kyber512 for key decapsulation.

In terms of key sizes, SIKE-p503 does very well, with 462 bytes for the public key, 402 bytes for the ciphertext and 434 bytes for the private key. If we use a compressed form, we can shrink them down even further to 197 bytes for the public key. SIKE looks a winner for key and ciphertext sizes, and much less than RSA and getting near ECC (64 bytes for the public key and 32 bytes for the private key) [here]:

BIKE-L1 doesn’t do too badly, with 1541 bytes for the public key, 1,573 bytes for the ciphertext and 5,223 bytes for the private key [here]:

But, Classic McEliece really struggles for the size of its public key, with a massive 261,120 bytes for the smallest public key for the Level 1 security level. The ciphertext is small though, with only 128 bytes, and with a reasonable size for the private key (6,452 bytes).

SIKE

Supersingular Isogeny Key Encapsulation (SIKE) [4] is a post-quantum cryptography key encapsulation method for key exchange and is based on Supersingular Isogeny Diffie-Hellman (SIDH). It has a similar methodology to the Diffie-Hellman method but is quantum robust. It was created by Luca de Feo, David Jao and Jerome Plut [2][paper] and enhanced by Craig Costello, Patrick Longa, and Michael Naehrig at Microsoft [3][paper], and has one of the smallest key sizes for quantum robust cryptography methods (where the public key is 378 bytes and the private key is 434 bytes). In elliptic curve methods, the public key is only 32 bytes.

SIKE also supports perfect forward secrecy (PFS) and which stops the long-term key from being compromised, on the cracking of a single key (neither NTRU [here] Ring-LWS [here] are set up for PFS). The method is still relatively slow compared with elliptic curve methods (and requires around 50 million cycles of a processor). In this case, we will implement SIKEp434 (128-bit security), SIKEp503 and SIKEp751 (256-bit security).

The following is an outline of the code [here]:

A sample run for SIKEp434 is [here]:

Method: SIKEp434 
Seed for key exchange: 5C654D1BABF98CDFEABE56B235EA52FDEC1839DB9FC0AA143B0E7D5235AB8925DB73BE4B125032579F2BEE16F06E1167
Public Key (pk) = C813D012F6A8A8E4873945170EE49010166D5EE1B27CC2EB7BC3E9149B900D44 (first 32 bytes)
Private key (sk) = D21D2742521EF908C4BB621F858E49F773D5184554F1CF5DFD1C889FD62763E5 (first 32 bytes)
Cipher text (ct) = D2B28A66405C896ACBA843E1E144969055D4F06614E04C5D639BE0EFE28543A7 (first 32 bytes)
Shared key (Bob):	38FEF101B08A344A5AA462D139666ACE
Shared key (Alice):	38FEF101B08A344A5AA462D139666ACE
Length of Public Key (pk) = 330 bytes 
Length of Secret Key (pk)  = 44  bytes
Length of Cipher text (ct) = 346  bytes
Keys are the same

A sample run for SIKEp434 is [here]:

Method: SIKEp503 
Seed for key exchange: 74A5E508A3187CBE7D005EA27B819D78CEDE8C0FE02FFCACE277CCC17BFB79C4046C3DFD2541BA463A87E2ABD8AEDC2F
Public Key (pk) = 7F109D0EFFE2120F808BD8BE935C1438CC0A39D1BCADA650F0C1A564F693429B (first 32 bytes)
Private key (sk) = 59A8853A5D2C582863F57554D5AE0EFFF76FFF6E812CBA12E6675738E1D86A2A (first 32 bytes)
Cipher text (ct) = F5BDA6BAB3F12CC74D912E8B0B975D04E1763B1902D32F70DE9E1391E1B8CDB9 (first 32 bytes)
Shared key (Bob):	C1D5E520E4571C5F595FA6D7ED1EDB59CFDF7E26563DDC63
Shared key (Alice):	C1D5E520E4571C5F595FA6D7ED1EDB59CFDF7E26563DDC63
Length of Public Key (pk) = 378 bytes 
Length of Secret Key (pk)  = 56  bytes
Length of Cipher text (ct) = 402  bytes

A sample run for SIKEp751 [here]:

Method: SIKEp751 
Seed for key exchange: E7B1B58ED1098C6F1D91ACE00B7FBB4165ADCCBC17129992C42DBC5EAF6B628936701573D6C305DBCFB1259EAB78C6AB
Public Key (pk) = C3EC4A47C4DA001F484F6E30F2E479F7F33F470225ECFE0F63C6F914CDA6C652 (first 32 bytes)
Private key (sk) = 05A309A4CCF5A77BE8BF9CB76AC8AE31BA3F40813A2616484CDF7424D679E42D (first 32 bytes)
Cipher text (ct) = 7C43E5C0D906DA84F626E037099022916ABE481B39ABD01D84B6269642F95328 (first 32 bytes)
Shared key (Bob):	A81E89A4B679B3CAB207B0E5FE8C65985FC83D3C50144DC8D36A8678C5EDB5E7
Shared key (Alice):	A81E89A4B679B3CAB207B0E5FE8C65985FC83D3C50144DC8D36A8678C5EDB5E7
Length of Public Key (pk) = 564 bytes 
Length of Secret Key (pk)  = 80  bytes
Length of Cipher text (ct) = 596  bytes

McEliece

McEliece is a post-quantum key exchange mechanism and a finalist for the NIST PQC competition. This page uses various methods including mceliece348864, mceliece460896, mceliece6688128, mceliece6960119 and mceliece8192128. In McEliece methods, we have three main parameters: m, n and t. With mceliece348864, we have a Level 1 security level with a public key size of 261,120 bytes, a private key size of 6,492 bytes, and a ciphertext size of 128 bytes. mceliece460896 has a Level 3 security level with a public key size of 524,160 bytes, a private key size of 13,608 bytes, and a ciphertext size of 188 bytes. mceliece460896 has a Level 5 security level with a public key size of 1,0454,992 bytes, a private key size of 13,932 bytes, and a ciphertext size of 240 bytes.

The following is the code in Node.js [here]:

In the same run, Alice generates a public key and a private key. Bob encrypts a shared key for her, and she decrypts it with her private key. Notice that the public key is 261,120 bytes long:

Type:  mceliece348864
Public key (Bytes) 261120
Public key (first 32 bytes) 7a85c0e46bad023b001f3b846c310fca2c82390304a1a989f68a1f7e7aabe20a
Private key size (Bytes): 261120
Private key (Bytes) 6452
Private key (first 32 bytes) af77ca39045954ebab244f0cd1b91a5a2b3ed379027aa430bd58f90dee4f8bda
Private key size (Bytes): 6452
Bob sends encrypted key: d68e8c189218e6811bc7c1649c4ac56b6116dceaa5e227155d711857bd4fc142aea38d06967e7dc364710f9b4d0674bd4b697cdd83e84c93df893b15a7dd9297eed9db785a06358a283f1d2c55f710e7dedb8fa4ec661514dc248250f4ca0cec9c2e711769f56986f0116e443607099473bbe3db1a37bc1199028025b9f5efb0
Encrypted key size (Bytes): 128
Bob key: 7da562dcbb7b4fef190bb0bd0eca87fd1b77951e452a89ff8eda18e616faca49
Alice decrypts key: 7da562dcbb7b4fef190bb0bd0eca87fd1b77951e452a89ff8eda18e616faca49

Conclusions

And so, SIKE and BIKE look reasonable for their performance and key/cipher sizes, but McEliece is let down with the key generation performance and for the public key size. Another major factor is the Classic McEliece has been around for a few decades, while the isogeny methods of SIKE and BIKE are fairly new. This means that the security of McEliece is probably more reliable than SIKE and BIKE. So each of them has a chance, with BIKE looking the best compromise, but there could be advancements in isogeny-based methods that could improve their performance.

And, in the title, I say “also-rans”, but they are not, as they actually progress to the next round. All three of these methods have a chance to become a powerful key exchange mechanism in a post-quantum era.

Reference

[1] Costello, C. (2017). An introduction to supersingular isogeny-based cryptography. ECC. [paper]

[2] Jao, D., & De Feo, L. (2011, November). Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In International Workshop on Post-Quantum Cryptography (pp. 19–34). Springer, Berlin, Heidelberg. [paper]

[3] Costello, C., Longa, P., & Naehrig, M. (2016, August). Efficient algorithms for supersingular isogeny Diffie-Hellman. In Annual International Cryptology Conference (pp. 572–601). Springer, Berlin, Heidelberg. [paper]

[4] Douglas Stebila, Introduction to post-quantum cryptography and learning with errors, Summer School on real-world crypto and privacy, Šibenik, Croatia, June 11, 2018 [slides].