Shorter Signatures Based on Tailor-Made Minimalist Symmetric-Key Crypto
Christoph Dobraunig, Daniel Kales, Christian Rechberger, Markus Schofnegger, Greg Zaverucha · Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security · 2022
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.