MPCitH-based Signature for the RSD problem using a Hypercube

Abstract

Finding efficient signature schemes based on coding theory is an important issue for post-quantum cryptography. One can build signature schemes based on zero-knowledge proofs using the Stern protocol and its variants as demonstrated both in Hamming metric [1], [2] and rank metric [3], [4]. These constructions feature a high soundness error hence have a rather large signature size. Recently, some techniques based on secure Multi-Party Computation (MPC) have made it possible to lower this soundness error thus resulting in smaller signatures in both Hamming metric [5], [6] and rank metric [7], [8]. Even more recently, a hypercube-based approach has improved the Hamming metric approach [9]. In this paper, we adapt the idea of [9] to rank metric using the protocol from [8]. Given a fixed number of parties, this hypercube-based approach improves the performances of the underlying scheme. It is thus possible to consider additional trade-offs between sizes and performances thus reducing the signature size up to 4.5kB by increasing the number of parties of the MPC protocol.