International Association
for Cryptologic Research

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.