Weight of Polynomial Products Mod (Xn+1)-Application to the HQC Cryptosystem

We consider the following problem: given two random polynomials $x$ and $y$ in the ring $\F_2[X]/(X^n+1)$, our goal is to compute the expectation and variance of the weight of their product $x\cdot y$, where the weight of a binary polynomial is defined as the number of its nonzero coefficients. We consider two models for random polynomials $x$ and $y$: the \emph{uniform slice case} with fixed weights $w_x,w_y$, and the \emph{binomial case} where their coefficients are independent Bernoulli variables with success probabilities $p_x$ and $p_y$ respectively. Our work finds a direct application in the accurate analysis of the decryption failure rate for the code-based encryption scheme HQC \cite{HQC2025}. The original construction \cite{HQC2025} relied on heuristic arguments supported by experimental data. Later, \cite{Kawachi2020} provided a formally proven security bound, albeit a much weaker one than the heuristic estimate in \cite{HQC2025}. A fundamental limitation of both analyses is their restriction to the binomial case, a simplification that compromises the resulting security guarantees. Our analysis provides the first precise computation of the expectation and variance of $\weight(x\cdot y)$ across both the uniform slice and binomial models. The results confirm the soundness of the HQC security guarantees and allow for a more informed choice of the scheme parameters that optimizes the trade-off security and efficiency.