An official website of the United States government
Here’s how you know
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.
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 September 19, 2024)