Summary
2020
Session Number:C01
Session:
Number:C01-7
Hamming Weight of Product of Random Sparse Polynomials
Akinori Kawachi,
pp.368-371
Publication Date:2020/10/18
Online ISSN:2188-5079
PDF download
Summary:
Consider two random n-bit vectors x,y of which each coordinate is 1 with small probability e independently from the others. It is easy to see that the Hamming weight of their sum x+y is strongly concentrated around the expectation by the standard probability analysis for independent random variables such as the Chernoff bounds, that is, wt(x+y) is between 1.1E[wt(x+y)] and 0.9E[wt(x+y)] with probability 1-exp(-Omega(en)), where E[wt(x+y)]=2e(1-e). In this paper, we focus on the Hamming weight of their ``product" x*y defined as a product of polynomials over the ring F_2[t]/(t^n-1), which is utilized for construction of the post-quantum public-key encryption scheme HQC [Aguilar Melchor, et al. IEEE Trans. (2018)]. In the case of the product, the standard analysis does not work because of correlations among the coordinates of x*y. We prove weak concentration bounds for the Hamming weight of x*y from Chebyshev's inequality by analyzing the correlations. For example, we can show that x*y is between 1.1E[wt(x*y)] with probability 1-O(e^3n) for e=Omega(n^{-1/2}) from the bounds, where E[wt(x*y)]=(1-(1-2e^2)^n)n/2.