Paper 2012/293

New Transference Theorems on Lattices Possessing n^\epsilon-unique Shortest Vectors

Wei Wei, Chengliang Tian, and Xiaoyun Wang

Abstract

We prove three optimal transference theorems on lattices possessing $n^{\epsilon}$-unique shortest vectors which relate to the successive minima, the covering radius and the minimal length of generating vectors respectively. The theorems result in reductions between GapSVP$_{\gamma'}$ and GapSIVP$_\gamma$ for this class of lattices. Furthermore, we prove a new transference theorem giving an optimal lower bound relating the successive minima of a lattice with its dual. As an application, we compare the respective advantages of current upper bounds on the smoothing parameter of discrete Gaussian measures over lattices and show a more appropriate bound for lattices whose duals possess $\sqrt{n}$-unique shortest vectors.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. This paper hasn't been published anywhere.
Keywords
Transference theoremReductionGaussian measuresSmoothing parameter
Contact author(s)
wei-wei08 @ mails tsinghua edu cn
History
2012-06-03: received
Short URL
https://ia.cr/2012/293
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/293,
      author = {Wei Wei and Chengliang Tian and Xiaoyun Wang},
      title = {New Transference Theorems on Lattices Possessing n^\epsilon-unique Shortest Vectors},
      howpublished = {Cryptology ePrint Archive, Paper 2012/293},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/293}},
      url = {https://eprint.iacr.org/2012/293}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.