Skip to main content

NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.

Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.

U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Weak is Better: Tightly Secure Short Signatures from Weak PRFs

Published

Author(s)

Jacob M. Alperin-Sheriff, 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. Unfortunately, the scheme suffers from an infeasibly massive verification key and even more infeasibly slow signing and verification algorithms. In addition, it makes some questionable claims regarding quantum-safe security, and has a less-than-rigorous proof of security. We improve on their result, providing a rigorous proof of security, 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.
Citation
IACR ePrint
Volume
2017

Keywords

cryptography, lattice-based cryptography, post-quantum cryptography, digital signatures

Citation

Alperin-Sheriff, J. and Apon, D. (2017), Weak is Better: Tightly Secure Short Signatures from Weak PRFs, IACR ePrint, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=922105, https://eprint.iacr.org/2017/563 (Accessed October 8, 2025)

Issues

If you have any questions about this publication or are having problems accessing it, please contact [email protected].

Created June 7, 2017, Updated October 2, 2017
Was this page helpful?