The biggest surprise about HQC is that it’s not actually "new" in the sense of being a brand-new cryptographic construction; it’s a mature, well-understood scheme based on the hardness of the decoding problem in quasi-cyclic codes.
Let’s see HQC in action. Imagine Alice wants to send a secret message to Bob. Bob has a public key, and Alice uses it to encrypt her message.
Bob’s Public Key Generation:
Bob starts with a secret key, which is essentially a specific, structured code (a quasi-cyclic code defined by generator polynomials g and h). He then generates a public key, which is a more general, seemingly random matrix A and a vector s. The crucial part is that A is derived from g and h in a way that’s hard to reverse without knowing g and h.
{
"secret_key": {
"g": "0x1a2b3c...",
"h": "0x4d5e6f..."
},
"public_key": {
"A": "0x789abc...",
"s": "0xdef012..."
}
}
Alice’s Encryption:
Alice has a message m she wants to send. She picks a random error vector e (small weight) and a random secret vector r. She then computes:
u = r * A
v = r * s + m + e
Her ciphertext is the pair (u, v).
{
"ciphertext": {
"u": "0x345678...",
"v": "0x90abcd..."
}
}
Bob’s Decryption:
Bob receives (u, v). He uses his secret key s to compute:
v' = v - u * s
Substituting the definitions:
v' = (r * s + m + e) - (r * A) * s
v' = r * s + m + e - r * (A * s)
Because A and s are derived from Bob’s secret code, the term A * s is related to the code structure. Specifically, if A is the parity-check matrix and s is the syndrome, then A*s is related to the error locator polynomial or similar constructs. In HQC’s case, A is a random-looking matrix derived from the code’s structure, and s is a secret vector constructed using the code. The relationship A*s effectively cancels out the r*s term in a specific way due to the properties of quasi-cyclic codes.
The equation simplifies to:
v' = m + e
Bob knows m is a message (typically represented as a short vector or a codeword) and e is a small error vector. Since e is small, Bob can recover m by applying a decoding algorithm for his code to v', which is designed to remove small errors.
The core problem HQC solves is establishing a shared secret key for symmetric encryption (like AES) in a way that’s resistant to quantum computers. Traditional public-key cryptography (RSA, ECC) relies on problems like integer factorization or discrete logarithms, which quantum computers can solve efficiently using Shor’s algorithm. HQC, like other post-quantum KEMs, is based on mathematical problems believed to be hard even for quantum computers. The specific problem here is the hardness of decoding a random-looking linear code, especially quasi-cyclic codes.
The "quasi-cyclic" aspect of the codes is key. It means that if you take a codeword and cyclically shift it by a certain amount, it remains a codeword. This property allows for efficient encoding and decoding algorithms, which is crucial for performance. The public key A is constructed in a way that looks random, hiding the underlying structured code, but Bob can use his knowledge of the code structure (generator polynomials g and h) to efficiently perform the necessary operations and recover the message.
The choice of parameters for HQC (like the code length n, dimension k, and the nature of the error e) is critical for its security and efficiency. These parameters determine the size of the keys, ciphertexts, and the computational cost of encryption and decryption, while also providing a sufficient security margin against known classical and quantum attacks. The NIST selection process involved rigorous analysis of these parameters and the underlying cryptographic assumptions.
The "error" in HQC is not a random bit flip in the traditional sense of error correction; it’s a deliberate addition of a small number of "errors" (coefficients in the polynomial representation of the vector) to obscure the relationship between the public key and the secret key. When Bob decrypts, he essentially uses his knowledge of the code to "remove" these added errors, revealing the original message. The structure of quasi-cyclic codes allows this "error removal" to be done efficiently.
When you’re implementing HQC, understanding the exact polynomial representation of your message, secret key, and public key is paramount. The operations r * A and v - u * s are not just matrix multiplications in abstract; they are polynomial multiplications and additions over a finite field (typically GF(2) or GF(2^p)), and the "errors" are coefficients within these polynomials. The decoding step is a specific algorithm designed to find the original message polynomial given the noisy received polynomial v'.
The next hurdle you’ll encounter is integrating this KEM with a symmetric cipher to achieve authenticated encryption, as KEMs themselves only provide confidentiality.