Paper 2020/128
LegRoast: Efficient post-quantum signatures from the Legendre PRF
Ward Beullens and Cyprien Delpech de Saint Guilhem
Abstract
We introduce an efficient post-quantum signature scheme that relies on the one-wayness of the Legendre PRF. This "LEGendRe One-wAyness SignaTure" (LegRoast) builds upon the MPC-in-the-head technique to construct an efficient zero-knowledge proof, which is then turned into a signature scheme with the Fiat-Shamir transform. Unlike many other Fiat-Shamir signatures, the security of LegRoast can be proven without using the forking lemma, and this leads to a tight (classical) ROM proof. We also introduce a generalization that relies on the one-wayness of higher-power residue characters; the "POwer Residue ChaRacter One-wAyness SignaTure" (PorcRoast). LegRoast outperforms existing MPC-in-the-head-based signatures (most notably Picnic/Picnic2) in terms of signature size and speed. Moreover, PorcRoast outperforms LegRoast by a factor of 2 in both signature size and signing time. For example, one of our parameter sets targeting NIST security level I results in a signature size of 7.2 KB and a signing time of 2.8ms. This makes PorcRoast the most efficient signature scheme based on symmetric primitives in terms of signature size and signing time.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Post-Quantum digital signaturesLegendre PRFMPC-in-the-head
- Contact author(s)
-
ward beullens @ esat kuleuven be
cyprien delpechdesaintguilhem @ kuleuven be - History
- 2023-09-25: last of 2 revisions
- 2020-02-06: received
- See all versions
- Short URL
- https://ia.cr/2020/128
- License
-
CC BY