Buckle Up for a Faster $𝖱𝖸𝖣𝖤$: Performance Improvements for Rank-Based Signature

The MPC-in-the-Head paradigm is widely used to build post-quantum digital signatures as it provides a versatile way to design Proofs of Knowledge based on hard problems. Despite similarities among the MPC-in-the-Head based schemes, differences in size and performance persist among these schemes, fundamentally determined by choices in proof system parameters (such as the number of simulated parties and repetitions) and optimized implementation techniques. RYDE is a MPCitH based signature scheme relying on the hardness of the rank syndrome decoding problem. This work explores an alternative selection of parameters for RYDE looking for an optimal choice leading to efficient implementations by moving towards additional optimized AVX implementations for the underlying mathematical operations (e.g., field, vector, and matrix-related arithmetic). It also addresses another important performance bottleneck, stemming from the design choice in symmetric primitive instantiation for expanding seeds, committing messages, and sampling pseudo-random mathematical objects. Exploring the optimization boundaries of RYDE also helps maximizing the efficiency of other rank-based cryptosystems sharing similar underlying mathematical concepts. As a main result, our experiments show a considerable speedup in the signing and verification procedures of RYDE. For parameter sets corresponding to Fast variants, we achieve between 1.5x and 2.4x faster performances than the baseline RYDE without affecting signature sizes. For the Short variants, we observe between 3.8x and 5.5x faster running times at the cost of a limited overhead in signature sizes.