eprint.iacr.org
Thorns in Polynomial Convolution: Correlation, Large Deviations, and Applications
When estimating the decryption failure rate (DFR) of structured lattice-based cryptography, some schemes implicitly assume that the coefficients of the decryption noise are independent. In practice, however, the decryption noise typically contains terms arising from convolutions of small polynomials, which introduce correlations among coefficients. These correlations can create a non-negligible gap between independence-based estimates and empirical failure rates, leading to underestimated DFRs, overestimated security levels, and exploitable attack surfaces. They also obscure the effect of error-correcting mechanisms in structured lattice-based encryption designs. To date, there has been no practical framework for characterizing such correlations.
In this paper, we give the first systematic characterization of correlations among the coefficients of convolved polynomials with Gaussian coefficients, using the canonical embedding as the central viewpoint. We establish large-deviation results for the coefficients of the resulting polynomial. Our analysis shows that, as the norm grows, convolutional polynomials asymptotically concentrate near a finite set of fixed two-dimensional planes. This gives rise to directional tail structures in the n-dimensional joint probability density, which we call thorns.
As a direct application, we prove that existing decryption-failure attacks succeed precisely by forcing the noise to lie on these thorns. This phenomenon endows the noise with extremely strong correlations, ultimately triggering decryption failures. Furthermore, adopting the canonical embedding perspective allows us to comprehensively illustrate how the independence assumption distorts the true noise distribution. We prove that the independence assumption systematically underestimates the noise norm, and we derive an analytic expression for the probability density function of the Euclidean norm of the decryption noise.
