Short Signatures with Short Public Keys from Homomorphic Trapdoor Functions

We present a lattice-based stateless signature scheme provably secure in the standard model. Our scheme has a

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

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.