Paper 2020/128

LegRoast: Efficient post-quantum signatures from the Legendre PRF

Ward Beullens, KU Leuven
Cyprien Delpech de Saint Guilhem, KU Leuven

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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Post-Quantum Cryptography 2020
Post-Quantum digital signaturesLegendre PRFMPC-in-the-head
Contact author(s)
ward beullens @ kuleuven be
cyprien delpechdesaintguilhem @ kuleuven be
2023-09-25: last of 2 revisions
2020-02-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ward Beullens and Cyprien Delpech de Saint Guilhem},
      title = {{LegRoast}: Efficient post-quantum signatures from the Legendre {PRF}},
      howpublished = {Cryptology ePrint Archive, Paper 2020/128},
      year = {2020},
      doi = {10.1007/978-3-030-44223-1_8},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.