Paper 2017/563

Weak is Better: Tightly Secure Short Signatures from Weak PRFs

Jacob Alperin-Sheriff and Daniel Apon

Abstract

The Boyen-Li signature scheme [Asiacrypt'16] is a major theoretical breakthrough. Via a clever homomorphic evaluation of a pseudorandom function over their verification key, they achieve a reduction loss in security linear in the underlying security parameter and entirely independent of the number of message queries made, while still maintaining short signatures (consisting of a single short lattice vector). All previous schemes with such an independent reduction loss in security required a linear number of such lattice vectors, and even in the classical world, the only schemes achieving short signatures relied on non-standard assumptions. We improve on their result, providing a verification key smaller by a linear factor, a significantly tighter reduction with only a constant loss, and signing and verification algorithms that could plausibly run in about 1 second. Our main idea is to change the scheme in a manner that allows us to replace the pseudorandom function evaluation with an evaluation of a much more efficient weak pseudorandom function. As a matter of independent interest, we give an improved method of randomized inversion of the G gadget matrix [MP12], which reduces the noise growth rate in homomorphic evaluations performed in a large number of lattice-based cryptographic schemes, without incurring the high cost of sampling discrete Gaussians.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
weak pseudorandom functionssignatureslattice-based cryptography
Contact author(s)
jacobmas @ gmail com
History
2017-06-14: received
Short URL
https://ia.cr/2017/563
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/563,
      author = {Jacob Alperin-Sheriff and Daniel Apon},
      title = {Weak is Better: Tightly Secure Short Signatures from Weak PRFs},
      howpublished = {Cryptology ePrint Archive, Paper 2017/563},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/563}},
      url = {https://eprint.iacr.org/2017/563}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.