RYDE: A Digital Signature Scheme based on Rank-Syndrome-Decoding Problem with MPCitH Paradigm

2023/07/17 by Loïc Bidoux, Jesús-Javier Chi-Domínguez, Bidoux, Loïc +11
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge

paper · pdf · doi:10.48550/arxiv.2307.08726

openalex publication_date 2023/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a signature scheme based on the Syndrome-Decoding problem in rank metric. It is a construction from multi-party computation (MPC), using a MPC protocol which is a slight improvement of the linearized-polynomial protocol used in [Fen22], allowing to obtain a zero-knowledge proof thanks to the MPCitH paradigm. We design two different zero-knowledge proofs exploiting this paradigm: the first, which reaches the lower communication costs, relies on additive secret sharings and uses the hypercube technique [AMGH+22]; and the second relies on low-threshold linear secret sharings as proposed in [FR22]. These proofs of knowledge are transformed into signature schemes thanks to the Fiat-Shamir heuristic [FS86].

Related

• MIRA: a Digital Signature Scheme based on the MinRank problem and the MPC-in-the-Head paradigm
• RankSign: an efficient signature algorithm based on the rank metric
• TCitH- and VOLEitH-based Signatures from Restricted Decoding
• Compact Post-Quantum Signatures from Proofs of Knowledge leveraging Structure for the PKP, SD and RSD Problems
• Code-based Signatures from New Proofs of Knowledge for the Syndrome Decoding Problem