Paper 2015/1132

Tighter Security for Efficient Lattice Cryptography via the Rényi Divergence of Optimized Orders

Katsuyuki Takashima and Atsushi Takayasu


In security proofs of lattice based cryptography, bounding the closeness of two probability distributions is an important procedure. To measure the closeness, the Rényi divergence has been used instead of the classical statistical distance. Recent results have shown that the Rényi divergence offers security reductions with better parameters, e.g. smaller deviations for discrete Gaussian distributions. However, since previous analyses used a fixed order Rényi divergence, i.e., order two, they lost tightness of reductions. To overcome the deficiency, we adaptively 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 than the statistical distance based analysis and the reductions are tighter than those of previous Rényi divergence based analyses. As applications, we show tighter security reductions for sampling discrete Gaussian distributions with smaller precomputed tables for Bimodal Lattice Signature Scheme (BLISS), and the variants of learning with errors (LWE) problem and the small integer solution (SIS) problem called k-LWE and k-SIS, respectively.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. ProvSec 2015
lattice based cryptographytight reductionRényi divergencesampling discrete GaussianBLISSLWESIS
Contact author(s)
a-takayasu @ it k u-tokyo ac jp
2015-11-27: revised
2015-11-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Katsuyuki Takashima and Atsushi Takayasu},
      title = {Tighter Security for Efficient Lattice Cryptography via the Rényi Divergence of Optimized Orders},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1132},
      year = {2015},
      doi = {10.1007/978-3-319-26059-4},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.