Zero knowledge protocols and signatures from the restricted syndrome decoding problem

DOI10.1007/978-3-031-57722-2_8MaRDI QIDQ6635771zbMATH OpenFDO

Authors Marco Baldi, Sebastian Bitzer, Alessio Pavoni, Paolo Santini, Antonia Wachter-Zeh, Violetta Weger

Publication date 12 November 2024

Full work available at URL https://doi.org/10.1007/978-3-031-57722-2_8

zbMATH Keywords

code-based cryptographypost-quantum cryptographyrestricted errorssignature schemesyndrome decoding problem

Mathematics Subject Classification ID

Quantum cryptography (quantum-theoretic aspects) (81P94) Source coding (94A29) Cryptography (94A60) Authentication, digital signatures and secret sharing (94A62)

Recommendations

• Syndrome decoding in the head: shorter signatures from zero-knowledge proofs
• Shared permutation for syndrome decoding: new zero-knowledge protocol and code-based signature
• Short signatures from regular syndrome decoding in the head
• \textsf{ReSolveD}: shorter signatures from regular syndrome decoding and VOLE-in-the-head

Cites work

• A new identification scheme based on syndrome decoding
• A Statistical Decoding Algorithm for General Linear Block Codes
• A zero-knowledge identification scheme based on the q-ary syndrome decoding problem
• An Attack on Some Signature Schemes Constructed from Five-Pass Identification Schemes
• How To Prove Yourself: Practical Solutions to Identification and Signature Problems
• scientific article; zbMATH DE number 5485433 (Why is no real title available?)
• scientific article; zbMATH DE number 4112524 (Why is no real title available?)
• scientific article; zbMATH DE number 1406778 (Why is no real title available?)
• Improved Generic Algorithms for Hard Knapsacks
• Maximum distance<tex>q</tex>-nary codes
• On the inherent intractability of certain coding problems (Corresp.)
• Sigma protocols for MQ, PKP and SIS, and fishy signature schemes
• Some new NP-complete coding problems
• Statistical decoding 2.0: reducing decoding to LPN
• Two decoding algorithms for linear codes

Cited in

(11)

• A new algebraic approach to the regular syndrome decoding problem and implications for PCG constructions
• Short signatures from regular syndrome decoding in the head
• Syndrome decoding in the head: shorter signatures from zero-knowledge proofs
• \textsf{ReSolveD}: shorter signatures from regular syndrome decoding and VOLE-in-the-head
• MODRED: a code-based non-interactive key exchange protocol
• Correlation power analysis of LESS and CROSS
• A new path to code-based signatures via identification schemes with restricted errors
• A zero-knowledge proof for the syndrome decoding problem in the Lee metric
• Cross-paradigm models of restricted syndrome decoding with application to CROSS
• A security analysis of restricted syndrome decoding problems
• A BKW-style solver for the restricted syndrome decoding problem

This page was built for publication: Zero knowledge protocols and signatures from the restricted syndrome decoding problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6635771)