# Understanding a method of vector multiplication

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?

## 1 Answer

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!