Paper 2025/2180

Weight of Polynomial Products Mod $(X^n+1)$-Application to the HQC Cryptosystem-

Abstract

We consider the problem of computing the variance and tail probability bounds for the weight of the product $z = x \cdot y$ of two random polynomials $x, y \in \F_2[X]/(X^n+1)$, where the weight of a binary polynomial is defined as the number of its nonzero coefficients. We investigate two probabilistic models for $x$ and $y$: the \emph{uniform slice} model, where the weights are fixed to $w_x$ and $w_y$, and the \emph{binomial} model, where the coefficients are independent Bernoulli variables with parameters $p_x$ and $p_y$. Our analysis is directly motivated by the need for accurate security analysis of the error vector of the HQC code-based encryption scheme. Prior work has progressed from heuristic arguments backed by extensive simulations to exact computations of the probability mass function (PMF) of the weight of the error vector; however, these computations were largely restricted to the uniform slice setting. We adopt a different approach, leveraging the full covariance structure of the product vector $z$ (i.e., the pairwise covariances of its coefficients) to derive tight, rigorously proven bounds on the tail probabilities of its weight for both the uniform and binomial models. These results confirm HQC's security guarantees and, moreover, reveal additional symmetry properties of the HQC error vector that are desirable for cryptographic design.