Paper 2017/995

A signature scheme from Learning with Truncation

Jeffrey Hoffstein, Jill Pipher, William Whyte, and Zhenfei Zhang

Abstract

In this paper we revisit the modular lattice signature scheme and its efficient instantiation known as pqNTRUSign. First, we show that a modular lattice signature scheme can be based on a standard lattice problem. As the fundamental problem that needs to be solved by the signer or a potential forger is recovering a lattice vector with a restricted norm, given the least significant bits, we refer to this general class of problems as the “learning with truncation” problem. We show that by replacing the uniform sampling in pqNTRUSign with a bimodal Gaussian sampling, we can further reduce the size of a signature. As an example, we show that the size of the signature can be as low as 4608 bits for a security level of 128 bits. The most significant new contribution, enabled by this Gaussian sam- pling version of pqNTRUSign, is that we can now perform batch verifi- cation, which allows the verifier to check approximately 2000 signatures in a single verification process.

Note: Adding sections for transcript simulation. Also minor typos.

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
lattice-based signatureslearning with truncationroundingNTRUrejection sampling
Contact author(s)
zzhang @ onboardsecurity com
History
2017-10-30: revised
2017-10-11: received
See all versions
Short URL
https://ia.cr/2017/995
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/995,
      author = {Jeffrey Hoffstein and Jill Pipher and William Whyte and Zhenfei Zhang},
      title = {A signature scheme from Learning with Truncation},
      howpublished = {Cryptology ePrint Archive, Paper 2017/995},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/995}},
      url = {https://eprint.iacr.org/2017/995}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.