Paper 2021/692

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

Christoph Dobraunig, Daniel Kales, Christian Rechberger, Markus Schofnegger, and Greg Zaverucha

Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision.ACM CCS 2022
Keywords
digital signaturessymmetric-key cryptographypost-quantum cryptographyMPC-in-the-head
Contact author(s)
daniel kales @ tugraz at
gregz @ microsoft com
christoph dobraunig @ lamarr at
christian rechberger @ tugraz at
markus schofnegger @ tugraz at
History
2022-04-25: revised
2021-05-28: received
See all versions
Short URL
https://ia.cr/2021/692
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/692,
      author = {Christoph Dobraunig and Daniel Kales and Christian Rechberger and Markus Schofnegger and Greg Zaverucha},
      title = {Shorter Signatures Based on Tailor-Made Minimalist Symmetric-Key Crypto},
      howpublished = {Cryptology ePrint Archive, Paper 2021/692},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/692}},
      url = {https://eprint.iacr.org/2021/692}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.