Paper 2014/804

Short Signatures With Short Public Keys From Homomorphic Trapdoor Functions

Jacob Alperin-Sheriff

Abstract

We present a lattice-based stateless signature scheme provably secure in the standard model. Our scheme has a \emph{constant} number of matrices in the public key and a single lattice vector (plus a tag) in the signatures. The best previous lattice-based encryption schemes were the scheme of Ducas and Micciancio (CRYPTO 2014), which required a logarithmic number of matrices in the public key and that of Bohl et. al (J. of Cryptology 2014), which required a logarithmic number of lattice vectors in the signature. Our main technique involves using fully homomorphic computation to compute a degree $d$ polynomial over the tags hidden in the matrices in the public key. In the scheme of Ducas and Micciancio, only functions \emph{linear} over the tags in the public key matrices were used, which necessitated having $d$ matrices in the public key. As a matter of independent interest, we extend Wichs' (eprint 2014) recent construction of homomorphic trapdoor functions into a primitive we call puncturable homomorphic trapdoor functions (PHTDFs). This primitive abstracts out most of the properties required in many different lattice-based cryptographic constructions. We then show how to combine a PHTDF along with a function satisfying certain properties (to be evaluated homomorphically) to give an eu-scma signature scheme.

Note: Fixed minor error in the paper

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in PKC 2015
Keywords
latticesdigital signatureshomomorphic cryptography
Contact author(s)
jacobmas @ gmail com
History
2015-05-13: last of 2 revisions
2014-10-11: received
See all versions
Short URL
https://ia.cr/2014/804
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/804,
      author = {Jacob Alperin-Sheriff},
      title = {Short Signatures With Short Public Keys From Homomorphic Trapdoor Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2014/804},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/804}},
      url = {https://eprint.iacr.org/2014/804}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.