Understanding a method of vector multiplication

Question

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

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):
                continue
            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?

Answer 1

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!