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,