The security of the code-based signature scheme based on the Stern identification protocol

V. V. Vysotskaya ; I. V. Chizhov

Prikladnaâ diskretnaâ matematika, no. 3 (2022), pp. 67-90.

Résumé

The paper provides a complete description of the digital signature scheme based on the Stern identification protocol. We also present the proof of the existential unforgeability of the scheme under the chosen message attack (EUF-CMA) in the random oracle model (ROM). Finally, we discuss the choice of the signature parameters, in particular providing 70-bit security.

Détail

Keywords: post-quantum cryptography, code-based cryptography, digital signature, Stern's scheme, provable security, EUF-CMA security.
Mots-clés : Fiat-Shamir transform

Bibliographie

[1] Shor P. V., “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM J. Computing, 26:5 (1997), 1484–1509 | DOI | MR | Zbl

[2] NIST PQC Call for Proposals, , 2016 https://csrc.nist.gov/Projects/post-quantum-cryptography/Post-Quantum-Cryptography-Standardization/Call-for-Proposals

[3] Lee W., Kim Y.-S., Lee Y.-W., and No J.-S., Post quantum signature scheme based on modified Reed — Muller code pqsigRM, First round submission to the NIST post-quantum cryptography call, 2017 https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/pqsigRM.zip

[4] Fukushima K., Roy P. S., Xu R., et al., Supporting documentation of RaCoSS (Random Code-based Signature Scheme), First round submission to the NIST post-quantum cryptography call, 2017 https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/RaCoSS.zip

[5] Aragon N., Gaborit P., Hauteville A., et al., RankSign — a signature proposal for the NIST's call, First round submission to the NIST post-quantum cryptography call, 2017 https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/RankSign.zip

[6] Debris-Alazard T. and Tillich J.-P., “Two attacks on rank metric code-based schemes: RankSign and an IBE scheme”, LNCS, 11272, 2018, 62–92 | MR | Zbl

[7] Lee Y., Lee W., Kim Y. S., and No J.-S., “Modified pqsigRM: RM code-based signature scheme”, IEEE Access, 8 (2020), 177506–177518 | DOI

[8] Roy P. S., Morozov K., Fukushima K., et al., “Code-based signature scheme without trapdoors”, IEICE Tech. Rep., 118:151 (2018), 17–22

[9] Xagawa K., Practical Attack on RaCoSS-R, Cryptology Archive, Report 2018/831, , 2018 http://eprint.iacr.org/

[10] Kabatianskii G., Krouk E., and Smeets B., “A digital signature scheme based on random error-correcting codes”, LNCS, 1355, 1997, 161–167 | MR | Zbl

[11] Cayrel P.-L., Otmani A., and Vergnaud D., “On Kabatianskii — Krouk — Smeets signatures”, LNCS, 4547, 2007, 237–252 | MR

[12] Stern J., Can one design a signature scheme based on error-correcting codes?, LNCS, 917, 1995, 424–426 | MR | Zbl

[13] Courtois N., Finiasz M., and Sendrier N., “How to achieve a McEliece-based digital signature scheme”, LNCS, 2248, 2001, 157–174 | MR | Zbl

[14] McEliece R. J., “A public-key cryptosystem based on algebraic coding theory”, DSN Progress Report, 42–44 (1978), 114–116

[15] Niederreiter H., “Knapsack-type cryptosystems and algebraic coding theory”, Problems Control Inform. Theory, 15:2 (1986), 159–166 | MR | Zbl

[16] Dallot L., “Towards a concrete security proof of Courtois, Finiasz and Sendrier signature scheme”, LNCS, 4945, 2008, 65–77 | Zbl

[17] Debris-Alazard T., Sendrier N., and Tillich J.-P., “Wave: a new family of trapdoor one-way preimage sampleable functions based on codes”, LNCS, 11921, 2019, 21–51 | Zbl

[18] Fiat A. and Shamir A., “How to prove yourself: practical solutions to identification and signature problems”, LNCS, 263, 1987, 186–194 | MR | Zbl

[19] Stern J., “A new identification scheme based on syndrome decoding”, LNCS, 773, 1994, 13–21 | Zbl

[20] Jain A., Krenn S., Pietrzak K., and Tentes A., “Commitments and efficient zero-knowledge proofs from learning parity with noise”, LNCS, 7658, 2012, 663–680 | MR | Zbl

[21] Cayrel P.-L., Véron P., and El Y. A. S. M., “A zero-knowledge identification scheme based on the $q$-ary SD problem”, LNCS, 6544, 2010, 171–186 | MR

[22] Lyubashevsky V., “Lattice signatures without trapdoors”, LNCS, 7237, 2012, 738–755 | MR | Zbl

[23] Aragon N., Blazy O., Gaborit P., et al., “Durandal: a rank metric based signature scheme”, LNCS, 11478, 2019, 728–758 | MR | Zbl

[24] Overbeck R. and Sendrier N., “Code-based cryptography”, Post-Quantum Cryptography, 2009, 95–145 | DOI | MR | Zbl

[25] Roy P. S., Morozov K., Fukushima K., and Kiyomoto S., Evaluation of Code-Based Signature Schemes, Cryptology Archive, Report 2019/544, , 2019 https://eprint.iacr.org/

[26] El Y. A. S. M., Cayrel P.-L., El B. R., and Hoffmann G., “Code-based identification and signature schemes in software”, LNCS, 8128, 2013, 122–136

[27] Pointcheval D. and Stern J., “Security proofs for signature schemes”, LNCS, 1070, 1996, 387–398 | MR | Zbl

[28] Berlekamp E., McEliece R., and van Tilborg H., “On the inherent intractability of certain coding problems (Corresp.)”, IEEE Trans. Inform. Theory, 24:3 (1978), 384–386 | DOI | MR | Zbl

[29] Both L. and May A., “Decoding linear codes with high error rate and its impact for LPN security”, LNCS, 10786, 2018, 25–46 | MR | Zbl

[30] Lebedev P. A., “Comparison of old and new cryptographic hash function national standards of Russian Federation on CPUs and NVIDIA GPUs”, Mat. Vopr. Kriptogr., 4:2 (2013), 73–80 | DOI