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)
PDF
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
2020-02-18: revised
2020-02-06: received
See all versions
Short URL
https://ia.cr/2020/128
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/128,
      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},
      note = {\url{https://eprint.iacr.org/2020/128}},
      url = {https://eprint.iacr.org/2020/128}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.