Cryptology ePrint Archive: Report 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.

Category / Keywords: lattices, digital signatures, homomorphic cryptography

Original Publication (with minor differences): IACR-PKC-2015

Date: received 6 Oct 2014, last revised 13 May 2015

Contact author: jacobmas at gmail com

Available format(s): PDF | BibTeX Citation

Note: Fixed minor error in the paper

Version: 20150513:212311 (All versions of this report)

Short URL: ia.cr/2014/804

Discussion forum: Show discussion | Start new discussion