In this work we do both: we improve certain symmetric-key primitives to better fit signature schemes, and we also propose a new signature scheme by co-designing a proof system and a new block cipher. 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. For example, we achieve signature sizes of around 10.8 to 14.2 KB for the 128-bit security level, 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 can argue that it is very likely 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, based on a new block cipher called Rain combined 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.