Shorter Signatures Based on Tailor-Made Minimalist Symmetric-Key Crypto

Christoph Erwin Dobraunig, Daniel Kales*, Christian Rechberger, Markus Schofnegger, Greg Zaverucha

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


Signature schemes based on the MPC-in-the-head approach (MPCitH) have either been designed by taking a proof system and selecting a suitable symmetric-key primitive (Picnic, CCS16), or starting with an existing primitive such as AES and trying to find the most suitable proof system (BBQ, SAC19 or Banquet, PKC21).
In this work we do both: we improve certain symmetric-key primitives to better fit existing signature schemes, and we also propose a new signature scheme that combines a new, minimalist one-way function with changes to a proof system to make their combination even more efficient. Our concrete results are as follows.

First, we show how to provably remove the need to include the key schedule of block ciphers. This simplifies schemes like Picnic and it also leads to the fastest and smallest AES-based signatures, where we achieve signature sizes of around 10.8 to 14.2 KB using AES-128, on average 10% shorter than Banquet and 15% faster.

Second, we investigate a variant of AES with larger S-boxes we call LSAES, for which we argue that it is likely to be at least as strong as AES, further reducing the size of AES-based signatures to 9.9 KB.

Finally, we present a new signature scheme, Rainier, combining a new one-way function called Rain with a Banquet-like proof system. To the best of our knowledge, it is the first MPCitH-based signature scheme which can produce signatures that are less than 5 KB in size; it also outperforms previous Picnic and Banquet instances in all performance metrics.
Original languageEnglish
Title of host publicationCCS 2022 - Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security
PublisherAssociation of Computing Machinery
Number of pages15
ISBN (Electronic)978-1-4503-9450-5
Publication statusPublished - 7 Nov 2022
Event29th ACM Conference on Computer and Communications Security: ACM CCS 2022 - Los Angeles, United States
Duration: 7 Nov 202211 Nov 2022

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221


Conference29th ACM Conference on Computer and Communications Security
Country/TerritoryUnited States
CityLos Angeles


  • Digital signatures
  • MPC-in-the-head
  • Post-quantum cryptography
  • Symmetric-key cryptography
  • mpc-in-the-head
  • post-quantum cryptography
  • symmetric-key cryptography
  • digital signatures

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications

Cite this