Recently, I attempted to implement the HQC Post-Quantum KEM in (almost) pure python. In the scheme specification whitepaper, it states the following:

Screencap from whitepaper stating that vectors in the scheme are represented as row vectors of dimension n over GF(2) or polynomials over GF(2)[X]/(X^n - 1). Their product is defined, over the vector space, as a version of the discrete convolution of the two binary vectors 1

Here is a simplified version of the function I used to calculate the vector product (the actual function is implemented using bit-twiddling but this makes it more readable):

def _convolute(b, a, l):
        aa = [int(c) for c in ('{0:0' + str(l) + 'b}').format(a)]
        bb = [int(c) for c in ('{0:0' + str(l) + 'b}').format(b)]
        out = [0] * l
        for i in range(l):
            if (aa[i] == 0):
            for j in range(l):
                out[(i + j) % l] ^= bb[j]
        return int(''.join([str(c) for c in out]), 2)

Here, l, is always going to be the cryptosystem parameter $n$. This is an attempt at implementation of the vector product method described above. The vector a is always going to be incredibly sparse (~100 1s), so the naive method works fine. I believe the actual implementation uses a constant-time method to avoid SC timing attacks, but I'm not too concerned with that now.

I implemented this, and the cryptosystem worked as expected, encryption and decryption were correct, and the essential arithmetic given in the correctness proof section of the whitepaper was also correct, so I didn't give it much thought.

However, revisiting the project I decided to actually test all the functions against the KAT data given in the submission package. From the 04/10/2019 submission, I checked against the hqc-256-3 data for the reference implementation.

For the values of x, y, and h given in the data, the value of $s = x + y \cdot h$ does not match against my implementation, so I decided to take a look at the function again. Using Sage to perform arithmetic in the quotient ring $\mathcal{R}$ defined in the whitepaper, my _convolute function does not agree with it (using the interpretation that vector bits correspond to coefficients of the polynomials). I can't check against the reference data as Sage appears to do the calculations too slowly and cannot take advantage of sparse polynomials, so I was using elements of smaller degree for testing.

In conclusion, where am I going wrong? Am I correctly interpreting/implementing the vector product method in the whitepaper with the convolute function? Is a direct comparison to multiplication in $\mathcal{R}$ misguided? Lastly, would anyone be able to provide an algorithm which definitely works for computing products in $\mathcal{R}$, preferably without using FFT or similar, and just done in a schoolbook method.

In addition, if my method is completely incorrect, to what extent is the cryptosystem actually weakened by this wrong product computation?


I can't completely answer your question, but I don't see how sage can't compute the polynomial multiplication - are you computing in the residue ring modulo $x^n + 1$?

The following executes within a few hundreds of milliseconds on my computer:

R.<x> = PolynomialRing(GF(2), "x")
RR.<z> = R.quo(x^57367 + 1)
RR.random_element() * RR.random_element()

Maybe you can use this to debug your implementation.

Hope I could help!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.