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

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. Contributions. In this work, we investigate three methods of reducing MPCitH signature sizes further, while simultaneously improving the performance of signing and verification. Our results cover a range of options from more conservative (but less performant), to more performant (but with stronger assumptions). • We investigate the use of AES as a public permutation in a single-key Even-Mansour construction. The use of a public constant for the AES key removes the need to calculate the AES key schedule as part of the MPC protocol, reducing the number of S-boxes (and therefore inversions) from 200 to 160 for AES-128, which leads to smaller signatures using the Banquet proof system. • In Banquet, the in-and outputs to the inverse functions are lifted from the AES field F 2 8 to a larger field F 2 8λ to reduce the soundness error of the protocol. This step leads to an increase in signature size, since elements