What Happens After Kyber? Meet BIKE, HQC and Classical Mceliece
What Happens After Kyber? Meet BIKE, HQC and Classical Mceliece
In the 3rd round of the NIST PQC competition, Kyber was selected for standardization for a key encapsulation method and thus looks to replace ECDH as a key exchange method. Overall, Kyber was by far the best method for the 3rd round candidates and was the fastest for key generation, and for encapsulation and decapsulation [here]:
NIST has since defined a 4th round and is now assessing BIKE, Classic McEliece, HQC and SIKE. Overall, SIKE has already been withdrawn as it was cracked at the end of Round 3. As we see from the above assessment, HQC and BIKE have a similar performance level, and both are code-based. For this, NIST wants a key encapsulation method which is not lattice-based [1]:
So, let’s implement BIKE and HQC.
BIKE
BIKE is a code-based key encapsulation mechanism and is based on QC-MDPC (Quasi-Cyclic Moderate Density Parity-Check). It has three security levels: Bike-128, Bike-192 and Bike-256. While Kyber-512 has a public key of 800 bytes, Bike128 uses a 1,541-byte public key. With the public key, Kyber512 has a key size of 1,632 bytes, and Bike128 has a public key of 3,114 bytes. The ciphertext for Kyber512 is 768 bytes, and in Bike128 it is 1,573 bytes.
We can now implement BIKE with [here]:
namespace Bike
{
using Org.BouncyCastle.Pqc.Crypto.Bike;
using Org.BouncyCastle.Security;
class Program
{
static void Main(string[] args)
{
try {
var size="128";
if (args.Length >0) size=args[0];
var random = new SecureRandom();
var keyGenParameters = new BikeKeyGenerationParameters(random, BikeParameters.bike128);
if (size=="192") keyGenParameters = new BikeKeyGenerationParameters(random, BikeParameters.bike192);
else if (size=="256") keyGenParameters = new BikeKeyGenerationParameters(random, BikeParameters.bike256);
var BikeKeyPairGenerator = new BikeKeyPairGenerator();
BikeKeyPairGenerator.Init(keyGenParameters);
var aKeyPair = BikeKeyPairGenerator.GenerateKeyPair();
var aPublic = (BikePublicKeyParameters)aKeyPair.Public;
var aPrivate = (BikePrivateKeyParameters)aKeyPair.Private;
var pubEncoded =aPublic.GetEncoded();
var privateEncoded = aPrivate.GetEncoded();
var bobBikeKemGenerator = new BikeKemGenerator(random);
var encapsulatedSecret = bobBikeKemGenerator.GenerateEncapsulated(aPublic);
var bobSecret = encapsulatedSecret.GetSecret();
var cipherText = encapsulatedSecret.GetEncapsulation();
var aliceKemExtractor = new BikeKemExtractor(aPrivate);
var aliceSecret = aliceKemExtractor.ExtractSecret(cipherText);
Console.WriteLine("Bike-{0}",size);
Console.WriteLine("Private key length:\t\t{0} bytes",aPrivate.GetEncoded().Length);
Console.WriteLine("Public key length:\t\t{0} bytes",aPublic.GetEncoded().Length);
Console.WriteLine("Ciphertext length:\t\t{0} bytes",cipherText.Length);
Console.WriteLine("\nAlice private (first 50 bytes):\t{0}",Convert.ToHexString(aPrivate.GetEncoded())[..100]);
Console.WriteLine("Alice public (first 50 bytes):\t{0}",Convert.ToHexString(aPublic.GetEncoded())[..100]);
Console.WriteLine("\nCipher (first 50 bytes):\t{0}",Convert.ToHexString(cipherText)[..100]);
Console.WriteLine("\nBob secret:\t\t{0}",Convert.ToHexString(bobSecret));
Console.WriteLine("Alice secret:\t\t{0}",Convert.ToHexString(aliceSecret));
} catch (Exception e) {
Console.WriteLine("Error: {0}",e.Message);
}
}
}
}and a sample run [here]:
Bike-128
Private key length: 3114 bytes
Public key length: 1541 bytes
Ciphertext length: 1573 bytes
Alice private (first 50 bytes): 0000000000000000000000002000000000000000000000000000000000000000000000000000000100000000000000000000
Alice public (first 50 bytes): 5620E78F6CDFD427EFDF068B6293D045071F607EBD01E958793648BE9D3E296E3FBBC96B0F911B13B1F68C1E05A5E8DF3A6F
Cipher (first 50 bytes): 07C839A703E6BE3B6BF055D93A568257C6F0FDD4B72EF02315A826A9AE8BEC8EE30832E816DBA92E225B75E2336A5A490ECD
Bob secret: CD1AA9D07DB5F5065034457CB792D928
Alice secret: CD1AA9D07DB5F5065034457CB792D928HQC
HQC is a code-based key encapsulation mechanism and is based on Hamming Quasi-Cyclic. It has three security levels: HQC-128, HQC-192 and HQC-256. While Kyber-512 has a public key of 800 bytes, HQC128 uses a 2,249-byte public key. With the private key, Kyber512 has a key size of 1,632 bytes, and Bike128 has a public key of 2,289 bytes. The ciphertext for Kyber512 is 768 bytes, and in HQC128 it is 4,497 bytes. We can see that the ciphertext for HQC is much larger than BIKE. Overall, HQC has slightly better performance over BIKE though.
We can now implement HQC with [here]:
namespace Hqc
{
using Org.BouncyCastle.Pqc.Crypto.Hqc;
using Org.BouncyCastle.Security;
class Program
{
static void Main(string[] args)
{
try {
var size="128";
if (args.Length >0) size=args[0];
var random = new SecureRandom();
var keyGenParameters = new HqcKeyGenerationParameters(random, HqcParameters.hqc128);
if (size=="192") keyGenParameters = new HqcKeyGenerationParameters(random, HqcParameters.hqc192);
else if (size=="256") keyGenParameters = new HqcKeyGenerationParameters(random, HqcParameters.hqc256);
var HqcKeyPairGenerator = new HqcKeyPairGenerator();
HqcKeyPairGenerator.Init(keyGenParameters);
var aKeyPair = HqcKeyPairGenerator.GenerateKeyPair();
var aPublic = (HqcPublicKeyParameters)aKeyPair.Public;
var aPrivate = (HqcPrivateKeyParameters)aKeyPair.Private;
var pubEncoded =aPublic.GetEncoded();
var privateEncoded = aPrivate.GetEncoded();
var bobHqcKemGenerator = new HqcKemGenerator(random);
var encapsulatedSecret = bobHqcKemGenerator.GenerateEncapsulated(aPublic);
var bobSecret = encapsulatedSecret.GetSecret();
var cipherText = encapsulatedSecret.GetEncapsulation();
var aliceKemExtractor = new HqcKemExtractor(aPrivate);
var aliceSecret = aliceKemExtractor.ExtractSecret(cipherText);
Console.WriteLine("Hqc-{0}",size);
Console.WriteLine("Private key length:\t\t{0} bytes",aPrivate.GetEncoded().Length);
Console.WriteLine("Public key length:\t\t{0} bytes",aPublic.GetEncoded().Length);
Console.WriteLine("Ciphertext length:\t\t{0} bytes",cipherText.Length);
Console.WriteLine("\nAlice private (first 50 bytes):\t{0}",Convert.ToHexString(aPrivate.GetEncoded())[..100]);
Console.WriteLine("Alice public (first 50 bytes):\t{0}",Convert.ToHexString(aPublic.GetEncoded())[..100]);
Console.WriteLine("\nCipher (first 50 bytes):\t{0}",Convert.ToHexString(cipherText)[..100]);
Console.WriteLine("\nBob secret:\t\t{0}",Convert.ToHexString(bobSecret));
Console.WriteLine("Alice secret:\t\t{0}",Convert.ToHexString(aliceSecret));
} catch (Exception e) {
Console.WriteLine("Error: {0}",e.Message);
}
}
}
}and a sample run [here]:
Hqc-128
Private key length: 2289 bytes
Public key length: 2249 bytes
Ciphertext length: 4497 bytes
Alice private (first 50 bytes): 51E5BB5E0280574195A735860D51EA035C77301B98B339FDF20B441CA8701D7B48CF6A516417736F0D198E70DEA7334E418B
Alice public (first 50 bytes): 0D198E70DEA7334E418BC9C70CC5D6FA296E828FAAE60DAB2F2A79AD505C799E614D9CE3BA93A1CC7840AAEDC323C5A6789E
Cipher (first 50 bytes): A36F6233072B79767CDE47DE4195A8D3FCD0FFAEA46DE77C7B36D3BE6B05950AF2EA29EBC4921D063283447F46193779420E
Bob secret: B7FCD4FEDFA99EAB046E75045B86F1732D8812AD439578170A4BEB3295DF1555439D4AB507654A0D1BD65CFB778912B5CA3E2EDC423C62421C68D4CDCDF4D536
Alice secret: B7FCD4FEDFA99EAB046E75045B86F1732D8812AD439578170A4BEB3295DF1555439D4AB507654A0D1BD65CFB778912B5CA3E2EDC423C62421C68D4CDCDF4D536Classic Mceliece
Classic Mceliece has five main modes: McEliece348864. McEliece460896 524. McEliece6688128, McEliece6960119 and McEliece8192128. With this, we have large public keys, and relatively large private keys, but a small ciphertext size:
Type Public key size (B) Secret key size (B) Ciphertext size (B)
McEliece348864 261,120 6,492 196 Code based
McEliece460896 524,160 13,608 156 Code based
McEliece6688128 1,044,992 13,932 208 Code based
McEliece6960119 1,047,319 13,948 194 Code based
McEliece8192128 1,357,824 14,120 208 Code basedUnfortunately, it is slow for key generation, but gives acceptable levels of encapsulation and decapsulation performance:
We can implement as [here]:
namespace Cmce
{
using Org.BouncyCastle.Pqc.Crypto.Cmce;
using Org.BouncyCastle.Security;
class Program
{
static void Main(string[] args)
{
try {
var size="mceliece460896r3";
if (args.Length >0) size=args[0];
var random = new SecureRandom();
var keyGenParameters = new CmceKeyGenerationParameters(random, CmceParameters.mceliece348864r3);
if (size=="mceliece460896r3") keyGenParameters = new CmceKeyGenerationParameters(random, CmceParameters.mceliece460896r3);
else if (size=="mceliece6960119r3") keyGenParameters = new CmceKeyGenerationParameters(random, CmceParameters.mceliece6960119r3);
else if (size=="mceliece6688128r3") keyGenParameters = new CmceKeyGenerationParameters(random, CmceParameters.mceliece6688128r3);
else if (size=="mceliece8192128r3") keyGenParameters = new CmceKeyGenerationParameters(random, CmceParameters.mceliece8192128r3);
var CmceKeyPairGenerator = new CmceKeyPairGenerator();
CmceKeyPairGenerator.Init(keyGenParameters);
var aKeyPair = CmceKeyPairGenerator.GenerateKeyPair();
var aPublic = (CmcePublicKeyParameters)aKeyPair.Public;
var aPrivate = (CmcePrivateKeyParameters)aKeyPair.Private;
var pubEncoded =aPublic.GetEncoded();
var privateEncoded = aPrivate.GetEncoded();
var bobCmceKemGenerator = new CmceKemGenerator(random);
var encapsulatedSecret = bobCmceKemGenerator.GenerateEncapsulated(aPublic);
var bobSecret = encapsulatedSecret.GetSecret();
var cipherText = encapsulatedSecret.GetEncapsulation();
var aliceKemExtractor = new CmceKemExtractor(aPrivate);
var aliceSecret = aliceKemExtractor.ExtractSecret(cipherText);
Console.WriteLine("Cmce-{0}",size);
Console.WriteLine("Private key length:\t\t{0} bytes",aPrivate.GetEncoded().Length);
Console.WriteLine("Public key length:\t\t{0} bytes",aPublic.GetEncoded().Length);
Console.WriteLine("Ciphertext length:\t\t{0} bytes",cipherText.Length);
Console.WriteLine("\nAlice private (first 50 bytes):\t{0}",Convert.ToHexString(aPrivate.GetEncoded())[..100]);
Console.WriteLine("Alice public (first 50 bytes):\t{0}",Convert.ToHexString(aPublic.GetEncoded())[..100]);
Console.WriteLine("\nCipher (first 50 bytes):\t{0}",Convert.ToHexString(cipherText)[..100]);
Console.WriteLine("\nBob secret:\t\t{0}",Convert.ToHexString(bobSecret));
Console.WriteLine("Alice secret:\t\t{0}",Convert.ToHexString(aliceSecret));
} catch (Exception e) {
Console.WriteLine("Error: {0}",e.Message);
}
}
}
}And a sample run [here]:
Cmce-mceliece8192128
Private key length: 14120 bytes
Public key length: 1357824 bytes
Ciphertext length: 208 bytes
Alice private (first 50 bytes): 10FCB7ACD5F28BA1371728D4F8A4468E40C88306CF5505B841E984A86F6AF725FFFFFFFF00000000A405F8015B05380E6718
Alice public (first 50 bytes): 81E5EEDA642A34955CF33D5C4FBD9A400862BF4593DF255F5BBBEC9B6EC805861A9946A8B90D2635C812A7DE7B993D9A034E
Cipher (first 50 bytes): 5C911606AFDB30BA16F914364DF2B1949C19A827FF70BC8B64B03AD0F2C9AE53FD1C3A4161EE01632358EF851D00047F334A
Bob secret: FCBAE584DA20AD5A17827D1BA233331169E9BA11B4369F91F43CBCADD91B128E
Alice secret: FCBAE584DA20AD5A17827D1BA233331169E9BA11B4369F91F43CBCADD91B128EConclusions
And, so, here are the key and ciphertext sizes:
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)
Bike128 1,541 3,114 1,573 Code-based
Bike192 3,083 6,198 3,115 Code-based
Bike256 5,122 10,276 5,154 Code-based
HQC128 2,249 2,289 4,497 Code-based
HQC192 4,522 4,562 9,042 Code-based
HQC256 7,245 7,285 14,485 Code-based
McEliece348864 261,120 6,492 196 Code based
McEliece460896 524,160 13,608 156 Code based
McEliece6688128 1,044,992 13,932 208 Code based
McEliece6960119 1,047,319 13,948 194 Code based
McEliece8192128 1,357,824 14,120 208 Code basedHQC and BIKE are neck and neck, while HQC was slightly better performance, BIKE has smaller key sizes and ciphertext. Mceliece, though, has a relatively slow key generation, but on a par with HQC and BIKE for encapsulation and decapsulation.
References
[1] Li, Y., & Wang, L. P. (2023). Security analysis of the Classic McEliece, HQC and BIKE schemes in low memory. Cryptology ePrint Archive.