Paper 2024/252
Short Signatures from Regular Syndrome Decoding, Revisited
Abstract
We revisit the construction of signature scheme using the MPC-in-the-head paradigm, and focus in particular on constructions from the regular syndrome decoding assumption, a well-known variant of the syndrome decoding assumption. We obtain two main contributions: – We observe that previous signatures in the MPC-in-the-head paradigm must rely on a salted version of the GGM puncturable pseudorandom function (PPRF) to avoid collision attacks. We design a new efficient PPRF construction provably secure in the multi-instance setting. The security analysis of our PPRF, in the ideal cipher model, is quite involved and forms a core technical contribution of our work. While previous constructions had to rely on a hash function, our construction uses only a fixed-key block cipher and is considerably more efficient as a result. Our improved PPRF can be used to speed up many MPC-in-the-head signatures, and illustrate it on two signatures: the recent SDitH (submitted to the NIST), and a new signature scheme that we introduce. – We introduce a new signature scheme from the regular syndrome decoding assumption, based on a new protocol for the MPC-in-the-head paradigm, which significantly reduces communication compared to previous works. Our scheme is conceptually simple, though its security analysis requires a delicate and nontrivial combinatorial analysis.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Code-based cryptographyDesign of Symmetric PrimitivesPost-Quantum CryptographySignature Schemes
- Contact author(s)
-
bui @ irif fr
carozza @ irif fr
couteau @ irif fr
dahmun goudarzi @ gmail com
joux @ cispa de - History
- 2024-02-16: approved
- 2024-02-15: received
- See all versions
- Short URL
- https://ia.cr/2024/252
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/252, author = {Dung Bui and Eliana Carozza and Geoffroy Couteau and Dahmun Goudarzi and Antoine Joux}, title = {Short Signatures from Regular Syndrome Decoding, Revisited}, howpublished = {Cryptology ePrint Archive, Paper 2024/252}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/252}}, url = {https://eprint.iacr.org/2024/252} }