Paper 2014/457

Transcript secure signatures based on modular lattices

Jeff Hoffstein, Jill Pipher, John M. Schanck, Joseph H. Silverman, and William Whyte

Abstract

We introduce a class of lattice-based digital signature schemes based on modular properties of the coordinates of lattice vectors. We also suggest a method of making such schemes transcript secure via a rejection sampling technique of Lyubashevsky (2009). A particular instantiation of this approach is given, using NTRU lattices. Although the scheme is not supported by a formal security reduction, we present arguments for its security and derive concrete parameters (first version) based on the performance of state-of-the-art lattice reduction and enumeration tech- niques. In the revision, we re-evaluate the security of first version of the parameter sets, under the hybrid approach of lattice reduction attack the meet-in-the-middle attack. We present new sets of parameters that are robust against this attack, as well as all previous known attacks.

Note: In this revision, we revisit the security of the proposed parameter sets of the NTRUMLS scheme. The re-evaluation of the security is based on an analysis of a hybrid attack on NTRU lattices. We also propose a new set of parameters that are immune to the above cryptanalysis. For a given security level, we increased the dimension of the NTRU lattice, while reducing the modulus q. This gives us a very low acceptance rate (between 2% to 8%) during the rejection sampling phase. This drawback can be mitigated with parallel computation.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. PQCRYPTO 2014
Keywords
lattice techniquesdigital signatures
Contact author(s)
wwhyte @ securityinnovation com
History
2016-04-29: revised
2014-06-15: received
See all versions
Short URL
https://ia.cr/2014/457
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/457,
      author = {Jeff Hoffstein and Jill Pipher and John M.  Schanck and Joseph H.  Silverman and William Whyte},
      title = {Transcript secure signatures based on modular lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2014/457},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/457}},
      url = {https://eprint.iacr.org/2014/457}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.