Tighter Security for Efficient Lattice Cryptography via the Renyi Divergence of Optimized Orders

摘要

In security proofs of lattice based cryptography, to bound the closeness of two probability distributions is an important procedure. To measure the closeness, the Renyi divergence has been used instead of the classical statistical distance. Recent results have shown that the Renyi divergence offers security reductions with better parameters, e.g. smaller deviations for discrete Gaussian distributions. However, since previous analyses used a fixed order Renyi divergence, i.e., order two, they lost tightness of reductions. To overcome the deficiency, we adap-tively optimize the orders based on the advantages of the adversary for several lattice-based schemes. The optimizations enable us to prove the security with both improved efficiency and tighter reductions. Indeed, our analysis offers security reductions with smaller parameters them the statistical distance based analysis and the reductions are tighter than that of previous Renyi divergence based analysis. As applications, we show tighter security reductions for sampling discrete Gaussian distributions with smaller precomputed tables for BLISS signatures, and variants of learning with errors (LWE) problem and small integer solution (SIS) problem called k-LWE and k-SIS.