What’s missing:

  • \(k < n - d + 1\), \(t = \lfloor(d-1)/2\rfloor\)
  • primitive root of finite field

Key generation

KEM key generation routine is a thin wrapper around PKE key generation routine. The PKE key generation routine works with four vectors \(\mathbf{x}, \mathbf{y}, \mathbf{h}, \mathbf{s}\). Each vector is an element in the finite field \(\mathbb{F}_2^n\) (or equivalently in the polynomial ring \(R = \mathbb{F}_2\left[x\right] / \langle x^n - 1 \rangle\)). In the reference implementation, they are typed with uint64_t[VEC_N_SIZE_64], where VEC_N_SIZE_64 = CEIL_DIV(PARAM_N, 64).

parameter code length \(n\) VEC_N_SIZE_64
HQC-1 17669 277
HQC-3 35851 561
HQC-5 57637 901

\(\mathbf{x}, \mathbf{y} \stackrel{\$}{\leftarrow} \mathcal{B}_\omega\) are sampled from the ball with Hamming weight \(\omega\), where \(\omega\) is 66, 100, 131 for the three security levels respectively.

There are two sampling routines in HQC. vect_sample_fixed_weight1 (\(\text{SampleFixedWeightVect\$}\) in written spec) samples fixed-weight vector uniformly, but uses rejection sampling. It is used in key generation. vect_sample_fixed_weight2 (\(\text{SampleFixedWeightVect}\)) samples fixed-weight vectors without using rejection sampling, but the output is slightly biased. This sampling routine is used in encryption. The specification claims that the bias does not affect the security of the scheme.

\(\mathbf{h} \stackrel{\$}{\leftarrow} \mathbb{F}_2^n\) is uniformly randomly sampled.

Finally \(\mathbf{s} \leftarrow \mathbf{y}\cdot\mathbf{h} + \mathbf{x}\). Here the arithmetics are all performed in the polynomial ring. The multiplication is big enough to actually warrant using Karatsuba.

A summary of data flow:

ek_seed, dk_seed ← keygen_seed
h ← ek_seed
x, y ← dk_seed
s ← h, x, y
ek ← ek_seed, s
dk ← dk_seed

Encryption

Similar to key generatino, the KEM encapsulation routine is a thin wrapper around the PKE encryption routine.

The encryption routines begins with sampling three fixed weight vectors

\[\begin{aligned} \mathbf{r}_1, \mathbf{r}_2 &\stackrel{\$}{\leftarrow} \mathcal{B}_{\omega_r} \\ \mathbf{e} &\stackrel{\$}{\leftarrow} \mathcal{B}_{\omega_e} \end{aligned}\]

All three vectors are in \(\mathbf{F}_2^n\) and sampled using the slightly biased vect_sample_fixed_weight2.

The ciphertext consists of two components:

\[\begin{aligned} \mathbf{u} &\leftarrow \mathbf{r}_1 + \mathbf{h} \cdot \mathbf{r}_2 \\ \mathbf{v} &\leftarrow \texttt{C.Encode}(\mathbf{m}) + \texttt{Truncate}( \mathbf{s}\cdot\mathbf{r}_2 + \mathbf{e}, l) \end{aligned}\]
  • \(\mathbf{r}_1, \mathbf{r}_2, \mathbf{e}\) are the fixed-weight vectors
  • \(\mathbf{h}\) is expanded from the ek_seed embedded in the public key
  • m has type uint8_t m[PARAM_SECURITY_BYTES]
  • C.Encode (and conversely C.Decode in the decryption routine) refers to the error correcting code. From the type of the ciphertext (see below) we can infer that \(\mathbf{u}, \mathbf{v}\) are in the finite field \(\mathbf{F}_2^n\). Details for the specific choice of code can be found in later section
// data_structures.h
typedef struct {
    uint64_t u[VEC_N_SIZE_64];
    uint64_t v[VEC_N_SIZE_64];
} ciphertext_pke_t;

Concatenation code

HQC uses a concatenated code for the C.Encode, C.Decode routines.

A concatenated code consists of an external code and an internal code. From a high level, encoding and decoding are function composition:

\[\begin{aligned} \texttt{CatCode.Encode} &= \texttt{IntCode.Encode} \circ \texttt{ExtCode.Encode} \\ \texttt{CatCode.Decode} &= \texttt{ExtCode.Decode} \circ \texttt{IntCode.Decode} \end{aligned}\]

For the external code, HQC uses Reed-Solomon code over \(\mathop{GF}(2^8)\) with dimension 32.