Paper 2019/1301

Modular lattice signatures, revisited

Dipayan Das, 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. 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 show that this problem is equivalent to the short integer solution (SIS) problem over the corresponding lattice. In addition, we show that by replacing the uniform sampling in pqNTRUSign with a bimodal Gaussian sampling, we can further reduce the size of a signature. An important new contribution, enabled by this Gaussian sampling version of pqNTRUSign, is that we can now perform batch verification of messages signed by the same public key, which allows the verifier to check approximately 24 signatures in a single verification process.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. designs, codes and cryptography
DOI
10.1007/s10623-019-00694-x
Keywords
lattice based signaturesNTRUsignature aggregation
Contact author(s)
dasdipayan crypto @ gmail com
jhoff @ math brown edu
wwhyte @ qti qualcomm com
zhenfei zhang @ hotmail com
History
2019-11-12: revised
2019-11-11: received
See all versions
Short URL
https://ia.cr/2019/1301
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1301,
      author = {Dipayan Das and Jeffrey Hoffstein and Jill Pipher and William Whyte and Zhenfei Zhang},
      title = {Modular lattice signatures, revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1301},
      year = {2019},
      doi = {10.1007/s10623-019-00694-x},
      note = {\url{https://eprint.iacr.org/2019/1301}},
      url = {https://eprint.iacr.org/2019/1301}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.