HQC Provides A Key Vehicle For The Future of the Internet
As you may know, Shor’s algorithm will break our existing public key methods, including for RSA and Elliptic Curve methods. For digital signatures NIST is looking to replace ECDSA, EdDSA and RSA with either ML-DSA (Dilitium), SLH-DSA (SPHINCS+) and Falcon, but for key exchange and public key encryption, we will replace RSA with ML-KEM (Kyber). And, so, we only have one key establishment method to pick from, for this, NIST has been investigating three other non-lattice methods: BIKE, HQC and McEliece. Recently, they announced that only HQC (Hamming Quasi-Cyclic) will be going forward [here]:
In the 3rd round of the NIST PQC competition for key establishment, Kyber was selected for standardisation and now defined as ML-KEM (FIPS 203). Overall, Kyber was by far the best method of the 3rd round candidates and was the fastest for key generation, for encapsulation and for decapsulation. NIST then moved to define a 4th round, and which assessed BIKE, Classic McEliece, HQC and SIKE. HQC and BIKE have similar performance levels, and both are code-based, whereas SIKE was withdrawn due to it being cracked for a weak set of parameters. McEliece, unfortunately, while highly secure and robust, it suffers from serious performance issues, so many thought that it was down to BIKE and HQC to compete for the next to be standardised.
The key sizes for Kyber and other PQC methods are:
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 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
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)HQC
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 create a Dotnet console project for .NET 8.0 with [here]:
dotnet new consoleFirst we install the Bouncy Castle library [here]:
dotnet add package BouncyCastle.CryptographyNext some code [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);
}
}
}
}A sample run showing the cipher text, and the public and private key is:
Hqc-128
Private key length: 2289 bytes
Public key length: 2249 bytes
Ciphertext length: 4497 bytes
Alice private (first 50 bytes): 4968C8C6628D90FA7E79A339BC16E7CEC9B723E9B067C5BB0EC82192E484092E02991B9B8E94DCD87936B7278B9D8BE375F8
Alice public (first 50 bytes): 7936B7278B9D8BE375F88E4ED9BE33F6B06A2CC90559FECF2ACB989DFBE8BF5AC1C260CCE367C1668C4C98D7E7E43BA921A8
Cipher (first 50 bytes): 191F37628688CB54F26217CE932831D6DD0C376F2634272A447548DE0E2DA14B9CFA04021C09C0A7C468F474B16D43AAFD69
Bob secret: 55A3B3632AE7C70ED3E17BF9D6F952482C61E28B2EE4159817703EE0AC469D00DB59EE7799F0D935C41DAF9F7826B33DFC76F1E95364B3088ABB23FDDF7BC2D2
Alice secret: 55A3B3632AE7C70ED3E17BF9D6F952482C61E28B2EE4159817703EE0AC469D00DB59EE7799F0D935C41DAF9F7826B33DFC76F1E95364B3088ABB23FDDF7BC2D2Why HQC and not BIKE?
Well, they are all code-based methods. BIKE and HQC have a similar performance level, but for McEliece, the key generation is extremely slow, but the encapsulation speed is around the same as BIKE and HQC [here]:
And for key sizes, again BIKE and HQC have similar key sizes (such as 3083 bytes for the public key in BIKE), but the public key for McEliece is large (but the private key is small) [here]:
We can see that BIKE has smaller keys than HQC, but HQC has better performance, so it looks like NIST went to performance over smaller keys.
Conclusion
So, it will be a long goodbye to ECDH, and a hello to ML-KEM and HQC. And, here is my revised migration map on possible future migrations:
