Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Post-Quantum digital signatures, Legendre PRF, MPC-in-the-head

Date: received 6 Feb 2020, last revised 18 Feb 2020

Contact author: ward beullens at esat kuleuven be, cyprien delpechdesaintguilhem@kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20200218:093623 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]