Top

Designs, Codes and Cryptography

Published in:

12-07-2021

Cryptanalysis of a code-based full-time signature

Authors: Nicolas Aragon, Marco Baldi, Jean-Christophe Deneuville, Karan Khathuria, Edoardo Persichetti, Paolo Santini

Published in: Designs, Codes and Cryptography | Issue 9/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We present an attack against a code-based signature scheme based on the Lyubashevsky protocol that was recently proposed by Song, Huang, Mu, Wu and Wang (SHMWW). The private key in the SHMWW scheme contains columns coming in part from an identity matrix and in part from a random matrix. The existence of two types of columns leads to a strong bias in the distribution of set bits in produced signatures. Our attack exploits such a bias to recover the private key from a bunch of collected signatures. We provide a theoretical analysis of the attack along with experimental evaluations, and we show that as few as 10 signatures are enough to be collected for successfully recovering the private key. As for previous attempts of adapting Lyubashevsky’s protocol to the case of code-based cryptography, the SHMWW scheme is thus proved unable to provide acceptable security. This confirms that devising secure code-based signature schemes with efficiency comparable to that of other post-quantum solutions (e.g., based on lattices) is still a challenging task.

previous article On ideal homomorphic secret sharing schemes and their decomposition

next article Proposing an MILP-based method for the experimental verification of difference-based trails: application to SPECK, SIMECK

Available only for authorised users

Aguilar C., Gaborit P., Schrek J.: A new zero-knowledge code based identification scheme with reduced communication. In: 2011 IEEE Information Theory Workshop, pp 648–652, (2011) https://doi.org/10.1109/ITW.2011.6089577.

Aragon N., Blazy O., Gaborit P., Hauteville A., Zémor G.: Durandal: a rank metric based signature scheme. In: Ishai Y., Rijmen V. (eds.) Advances in Cryptology - EUROCRYPT 2019, pp. 728–758. Springer International Publishing, Cham (2019).CrossRef

Aragon N., Deneuville J.C., Gaborit, P.: Another code-based adaptation of lyubashevsky’s signature cryptanalysed. Cryptology ePrint Archive, Report 2020/923, (2020) https://eprint.iacr.org/2020/923.

Baldi M., Khathuria K., Persichetti E., Santini P.: Cryptanalysis of a code-based signature scheme based on the Lyubashevsky framework. Cryptology ePrint Archive, Report 2020/905, (2020) https://eprint.iacr.org/2020/905.

Bardet M., Briaud P., Bros M., Gaborit P., Neiger V., Ruatta O., Tillich J.: An algebraic attack on rank metric code-based cryptosystems. In: Advances in Cryptology - EUROCRYPT 2020 Proceedings, Part III, Springer, LNCS, vol 12107, pp 64–93 (2020a).

Bardet M., Bros M., Cabarcas D., Gaborit P., Perlner R.A., Smith-Tone D., Tillich J.P., Verbel J.A.: Improvements of algebraic attacks for solving the rank decoding and MinRank problems. In: Moriai S, Wang H (eds) ASIACRYPT 2020, Part I, Springer, Heidelberg, LNCS, vol 12491, pp 507–536, (2020b) https://doi.org/10.1007/978-3-030-64837-4_17.

Barg S.: Some new NP-complete coding problems. Problemy Peredachi Informatsii 30(3), 23–28 (1994).MathSciNetMATH

Bellini E., Caullery F., Gaborit P., Manzano M., Mateu V.: Improved Veron identification and signature schemes in the rank metric. In: 2019 IEEE International Symposium on Information Theory (ISIT), pp 1872–1876 (2019).

Berlekamp E.R., McEliece R.J., van Tilborg H.C.A.: On the inherent intractability of certain coding problems (corresp.). IEEE Trans. Inf. Theory 24(3), 384–386 (1978). https://doi.org/10.1109/TIT.1978.1055873.CrossRefMATH

10.

Biasse J.F., Micheli G., Persichetti E., Santini P.: LESS is more: code-based signatures without syndromes. In: Nitaj A., Youssef A. (eds.) Progress in Cryptology - AFRICACRYPT 2020, pp. 45–65. Springer International Publishing, Cham (2020).CrossRef

11.

Cayrel P.L., Véron P., El Yousfi Alaoui S.M.: A zero-knowledge identification scheme based on the \(q\)-ary syndrome decoding problem. In: Selected Areas in Cryptography. Springer, Berlin, pp 171–186 (2011).

12.

Courtois N., Finiasz M., Sendrier N.: How to achieve a McEliece-based digital signature scheme. In: Boyd C (ed) ASIACRYPT 2001, Springer, Heidelberg, LNCS, vol 2248, pp 157–174, (2001) https://doi.org/10.1007/3-540-45682-1_10.

13.

Debris-Alazard T., Sendrier N., Tillich J.P.: Wave: A new family of trapdoor one-way preimage sampleable functions based on codes. In: Galbraith S.D., Moriai S. (eds) ASIACRYPT 2019, Part I, Springer, Heidelberg, LNCS, vol 11921, pp 21–51, (2019) https://doi.org/10.1007/978-3-030-34578-5_2.

14.

Deneuville J.C., Gaborit P.: Cryptanalysis of a code-based one-time signature. Des. Codes Cryptogr. 88(9), 1857–1866 (2020).MathSciNetCrossRef

15.

Faugere J.C., Gauthier-Umana V., Otmani A., Perret L., Tillich J.P.: A distinguisher for high-rate mceliece cryptosystems. IEEE Trans. Inf. Theory 59(10), 6830–6844 (2013).MathSciNetCrossRef

16.

Lyubashevsky V.: Lattice signatures without trapdoors. In: Pointcheval D., Johansson T. (eds) EUROCRYPT 2012, Springer, Heidelberg, LNCS, vol 7237, pp 738–755 (2012) https://doi.org/10.1007/978-3-642-29011-4_43.

17.

Lyubashevsky V., Ducas L., Kiltz E., Lepoint T., Schwabe P., Seiler G., Stehlé D.: CRYSTALS-DILITHIUM. Tech. rep., National Institute of Standards and Technology, available at https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions (2019).

18.

McEliece R.J.: A public-key system based on algebraic coding theory, Jet Propulsion Lab, DSN Progress Report 44, pp 114–116 (1978).

19.

National Institute of Standards and Technology (2017) NIST post-quantum standardization process. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography

20.

Persichetti E.: Improving the efficiency of code-based cryptography. PhD thesis, Department of Mathematics, University of Auckland (2012).

21.

Persichetti E.: Efficient one-time signatures from quasi-cyclic codes: a full treatment. Cryptography 2, 30 (2018). https://doi.org/10.3390/cryptography2040030.CrossRef

22.

Prange E.: The use of information sets in decoding cyclic codes. IRE Trans. Inf. Theory 8(5), 5–9 (1962).MathSciNetCrossRef

23.

Rivest R.L., Shamir A., Adleman L.M.: A method for obtaining digital signatures and public-key cryptosystems. Commun. Assoc. Comput. Mach. 21(2), 120–126 (1978).MathSciNetMATH

24.

Santini P., Baldi M., Chiaraluce F.: Cryptanalysis of a one-time code-based digital signature scheme. In: 2019 IEEE International Symposium on Information Theory (ISIT), pp 2594–2598 (2019).

25.

Shor P.W.: Algorithms for quantum computation: Discrete logarithms and factoring. In: 35th FOCS, IEEE Computer Society Press, pp 124–134 (1994) https://doi.org/10.1109/SFCS.1994.365700.

26.

Song Y., Huang X., Mu Y., Wu W., Wang H.: A code-based signature scheme from the Lyubashevsky framework. Theoret. Comput. Sci. 835, 15–30 (2020). https://doi.org/10.1016/j.tcs.2020.05.011.MathSciNetCrossRefMATH

27.

Stern J.: A new identification scheme based on syndrome decoding. In: Stinson D.R. (ed.) Advances in Cryptology – CRYPTO’ 93, pp. 13–21. Springer, Berlin Heidelberg (1994).CrossRef

28.

Véron P.: Improved identification schemes based on error-correcting codes. Appl. Algebra Eng. Commun. Comput. 8(1), 57–69 (1997). https://doi.org/10.1007/s002000050053.MathSciNetCrossRefMATH

Title: Cryptanalysis of a code-based full-time signature
Authors: Nicolas Aragon
Marco Baldi
Jean-Christophe Deneuville
Karan Khathuria
Edoardo Persichetti
Paolo Santini
Publication date: 12-07-2021
Publisher: Springer US
Published in: Designs, Codes and Cryptography / Issue 9/2021
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-021-00902-7

Springer Professional

Cryptanalysis of a code-based full-time signature

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 9/2021

Locally Recoverable Codes correcting many erasures over small fields

A new family of EAQMDS codes constructed from constacyclic codes

Construction of MDS twisted Reed–Solomon codes and LCD MDS codes

Generalized threshold secret sharing and finite geometry

On ideal homomorphic secret sharing schemes and their decomposition

MDS or NMDS self-dual codes from twisted generalized Reed–Solomon codes

Premium Partner