Welcome to the resource topic for 2014/804
Title:
Short Signatures With Short Public Keys From Homomorphic Trapdoor Functions
Authors: 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.
ePrint: https://eprint.iacr.org/2014/804
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .