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.
Download file
Counter downloads: 358
- Title The security of the code-based signature scheme based on the Stern identification protocol
- Headline The security of the code-based signature scheme based on the Stern identification protocol
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 57
- Date:
- DOI 10.17223/20710410/57/5
Keywords
post-quantum cryptography, code-based cryptography, digital signature, Stern’s scheme, Fiat-Shamir transform, provable security, EUF-CMA securityAuthors
References
Shor P. V. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J.Computing, 1997, vol.26, no. 5, pp. 1484-1509. The security of the code-based signature scheme based on the Stern identification protocol 89
https://csrc.nist.gov/Projects/post-quantum-cryptography/Post-Quantum-Cryptography-Standardization/Call-for-Proposals - NIST PQC Call for Proposals, 2016.
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.
Fukushima K., Roy P. S., Xu R., et al. Supporting documentation of RaCoSS (Random Codebased 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.
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.
Debris-Alazard T. and Tillich J.-P. Two attacks on rank metric code-based schemes: RankSign and an IBE scheme. LNCS, 2018, vol. 11272, pp. 62-92.
Lee Y., Lee W., Kim Y. S., and No J.-S. Modified pqsigRM: RM code-based signature scheme. IEEE Access, 2020, vol. 8, pp. 177506-177518.
Roy P. S., Morozov K., Fukushima K., et al. Code-based signature scheme without trapdoors. IEICE Tech. Rep., 2018, vol. 118, no. 151, pp. 17-22.
Xagawa K. Practical Attack on RaCoSS-R. Cryptology ePrint Archive, 2018, Report 2018/831, http://eprint.iacr.org/
Kabatianskii G., Krouk E., and Smeets B. A digital signature scheme based on random error-correcting codes. LNCS, 1997, vol. 1355, pp. 161-167.
Cayrel P.-L., Otmani A., and Vergnaud D. On Kabatianskii - Krouk - Smeets signatures. LNCS, 2007, vol. 4547, pp. 237-252.
Stern J. Can one design a signature scheme based on error-correcting codes? LNCS, 1995, vol. 917, pp. 424-426.
Courtois N., Finiasz M., and Sendrier N. How to achieve a McEliece-based digital signature scheme. LNCS, 2001, vol. 2248, pp. 157-174.
McEliece R. J. A public-key cryptosystem based on algebraic coding theory. DSN Progress Report, 1978, vol.42-44, pp.114-116.
Niederreiter H. Knapsack-type cryptosystems and algebraic coding theory. Problems Control Inform. Theory, 1986, vol. 15, no. 2, pp. 159-166.
Dallot L. Towards a concrete security proof of Courtois, Finiasz and Sendrier signature scheme. LNCS, 2008, vol. 4945, pp. 65-77.
Debris-Alazard T., Sendrier N., and Tillich J.-P. Wave: a new family of trapdoor one-way preimage sampleable functions based on codes. LNCS, 2019, vol. 11921, pp. 21-51.
Fiat A. and Shamir A. How to prove yourself: practical solutions to identification and signature problems. LNCS, 1987, vol. 263, pp. 186-194.
Stern J. A new identification scheme based on syndrome decoding. LNCS, 1994, vol. 773, pp.13-21.
Jain A., Krenn S., Pietrzak K., and Tentes A. Commitments and efficient zero-knowledge proofs from learning parity with noise. LNCS, 2012, vol. 7658, pp. 663-680.
Cayrel P.-L., Veron P., and El Y. A. S. M. A zero-knowledge identification scheme based on the q-ary SD problem. LNCS, 2010, vol. 6544, pp. 171-186.
Lyubashevsky V. Lattice signatures without trapdoors. LNCS, 2012, vol. 7237, pp. 738-755.
Aragon N., Blazy O, Gaborit P., et al. Durandal: a rank metric based signature scheme. LNCS, 2019, vol. 11478, pp. 728-758.
Overbeck R. and Sendrier N. Code-based cryptography. Post-Quantum Cryptography, 2009, pp.95-145.
Roy P. S., Morozov K., Fukushima K., and Kiyomoto S. Evaluation of Code-Based Signature Schemes. Cryptology ePrint Archive, 2019, Report 2019/544, https://eprint.iacr.org/
El Y.A.S.M., Cayrel P.-L., El B.R., and Hoffmann G. Code-based identification and signature schemes in software. LNCS, 2013, vol. 8128, pp. 122-136.
Pointcheval D. and Stern J. Security proofs for signature schemes. LNCS, 1996, vol. 1070, pp. 387-398.
Berlekamp E., McEliece R., and van Tilborg H. On the inherent intractability of certain coding problems (Corresp.). IEEE Trans. Inform. Theory, 1978, vol. 24, no. 3, pp. 384-386.
Both L. and May A. Decoding linear codes with high error rate and its impact for LPN security. LNCS, 2018, vol. 10786, pp. 25-46.
Lebedev P. A.Comparison of old and new cryptographic hash function national standards of Russian Federation on CPUs and NVIDIA GPUs. Mat. Vopr. Kriptogr., 2013, vol. 4, no. 2, pp. 73-80.
The security of the code-based signature scheme based on the Stern identification protocol | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2022. № 57. DOI: 10.17223/20710410/57/5
Download full-text version
Counter downloads: 134