Top

Published in:

2018 | OriginalPaper | Chapter

Code-Based Signature Schemes from Identification Protocols in the Rank Metric

Authors : Emanuele Bellini, Florian Caullery, Alexandros Hasikos, Marcos Manzano, Victor Mateu

Published in: Cryptology and Network Security

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

We present two code-based identification protocols and signature schemes in the rank metric, providing detailed pseudocode and selecting practical parameters. The proposals are derived from their analogue in the Hamming metric. We discuss their security in the post-quantum scenario. With respect to other signature schemes based on codes, our constructions maintain a similar efficiency, possess large but still practical signatures, and the smallest key and public key sizes.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Protean Signature Schemes

next chapter SETLA: Signature and Encryption from Lattices

Available only for authorised users

Here decoding is referring to the half distance decoding scenario (with \(n \approx 2k\)), which is the one of interest in the cryptographic setting.

Recall that the bounds provides d and than \(t=\left\lfloor (d-1)/2 \right\rfloor \).

Recall that RankSign scheme has been proven to be broken with the above mentioned parameters.

ISO/IEC 9798–5:2009 Information technology - Security techniques - Entity authentication - Part 5: Mechanisms using zero-knowledge techniques, December 2009. https://www.iso.org/standard/50456.html

El Yousfi Alaoui, S.M., Cayrel, P.-L., El Bansarkhani, R., Hoffmann, G.: Code-based identification and signature schemes in software. In: Cuzzocrea, A., Kittl, C., Simos, D.E., Weippl, E., Xu, L. (eds.) CD-ARES 2013. LNCS, vol. 8128, pp. 122–136. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40588-4_9CrossRef

Aragon, N., Gaborit, P., Hauteville, A., Tillich, J.P.: Improvement of generic attacks on the rank syndrome decoding problem (2017)

Baldi, M., Bianchi, M., Chiaraluce, F., Rosenthal, J., Schipani, D.: Using LDGM codes and sparse syndromes to achieve digital signatures. In: Gaborit, P. (ed.) PQCrypto 2013. LNCS, vol. 7932, pp. 1–15. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38616-9_1CrossRef

Barreto, P.S., Misoczki, R., Simplicio Jr., M.A.: One-time signature scheme from syndrome decoding over generic error-correcting codes. J. Syst. Softw. 84(2), 198–204 (2011)CrossRef

Berger, T.P., Cayrel, P.-L., Gaborit, P., Otmani, A.: Reducing key length of the McEliece cryptosystem. In: Preneel, B. (ed.) AFRICACRYPT 2009. LNCS, vol. 5580, pp. 77–97. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02384-2_6CrossRef

Bernstein, D.J.: Grover vs. McEliece. In: Sendrier, N. (ed.) PQCrypto 2010. LNCS, vol. 6061, pp. 73–80. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-12929-2_6CrossRef

Boneh, D., et al.: Random oracles in a quantum world. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 41–69. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_3CrossRef

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: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 171–186. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19574-7_12CrossRef

10.

Chabaud, F., Stern, J.: The cryptographic security of the syndrome decoding problem for rank distance codes. In: Kim, K., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 368–381. Springer, Heidelberg (1996). https://doi.org/10.1007/BFb0034862CrossRef

11.

Chen, L., et al.: Report on Post-quantum Cryptography (2016). https://doi.org/10.6028/NIST.IR.8105

12.

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

13.

Dagdelen, Ö., Galindo, D., Véron, P., Alaoui, S.M.E.Y., Cayrel, P.L.: Extended security arguments for signature schemes. Des. Codes Cryptogr. 78(2), 441–461 (2016)MathSciNetCrossRef

14.

Debris-Alazard, T., Tillich, J.P.: An attack on a NIST proposal: RankSign, a code-based signature in rank metric. arXiv preprint arXiv:1804.02556 (2018)

15.

Faugère, J.-C., Otmani, A., Perret, L., Tillich, J.-P.: Algebraic cryptanalysis of McEliece variants with compact keys. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 279–298. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_14CrossRef

16.

Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12CrossRef

17.

Finiasz, M.: Parallel-CFS. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 159–170. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19574-7_11CrossRef

18.

Finiasz, M., Sendrier, N.: Security bounds for the design of code-based cryptosystems. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 88–105. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_6CrossRef

19.

Gabidulin, E.M.: Theory of codes with maximum rank distance. Probl. Peredachi Informatsii 21(1), 3–16 (1985)MathSciNetMATH

20.

Gaborit, P., Ruatta, O., Schrek, J.: On the complexity of the rank syndrome decoding problem. IEEE Trans. Inf. Theory 62(2), 1006–1019 (2016)MathSciNetCrossRef

21.

Gaborit, P., Ruatta, O., Schrek, J., Zémor, G.: RankSign: an efficient signature algorithm based on the rank metric. In: Mosca, M. (ed.) PQCrypto 2014. LNCS, vol. 8772, pp. 88–107. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11659-4_6CrossRefMATH

22.

Gaborit, P., Schrek, J., Zémor, G.: Full cryptanalysis of the Chen identification protocol. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 35–50. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25405-5_3CrossRef

23.

Gaborit, P., Zémor, G.: On the hardness of the decoding and the minimum distance problems for rank codes. IEEE Trans. Inf. Theory 62(12), 7245–7252 (2016)MathSciNetCrossRef

24.

Google: A preview of Bristlecone, Google’s new quantum processor (2018). https://research.googleblog.com/2018/03/a-preview-of-bristlecone-googles-new.html

25.

Kabatianskii, G., Krouk, E., Smeets, B.: A digital signature scheme based on random error-correcting codes. In: Darnell, M. (ed.) Cryptography and Coding 1997. LNCS, vol. 1355, pp. 161–167. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0024461CrossRef

26.

Kiltz, E., Lyubashevsky, V., Schaffner, C.: A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10822, pp. 552–586. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_18CrossRefMATH

27.

Landais, G., Tillich, J.-P.: An efficient attack of a McEliece cryptosystem variant based on convolutional codes. In: Gaborit, P. (ed.) PQCrypto 2013. LNCS, vol. 7932, pp. 102–117. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38616-9_7CrossRef

28.

Lee, W., Kim, Y.S., Lee, Y.W., No, J.S.: Post quantum signature scheme based on modified Reed-Muller code, Post-Quantum Cryptography, Round 1 Submissions, November 2017. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions

29.

Loidreau, P.: Properties of codes in rank metric. arXiv preprint cs/0610057 (2006)

30.

Loidreau, P.: A new rank metric codes based encryption scheme. In: Lange, T., Takagi, T. (eds.) PQCrypto 2017. LNCS, vol. 10346, pp. 3–17. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59879-6_1CrossRef

31.

Löndahl, C., Johansson, T.: A new version of McEliece PKC based on convolutional codes. In: Chim, T.W., Yuen, T.H. (eds.) ICICS 2012. LNCS, vol. 7618, pp. 461–470. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34129-8_45CrossRef

32.

May, A., Ozerov, I.: On computing nearest neighbors with applications to decoding of binary linear codes. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 203–228. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_9CrossRef

33.

Misoczki, R., Barreto, P.S.L.M.: Compact McEliece keys from Goppa codes. In: Jacobson, M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 376–392. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-05445-7_24CrossRef

34.

Niederreiter, H.: Knapsack-type cryptosystems and algebraic coding theory. Prob. Control Inf. Theory 15(2), 159–166 (1986)MATH

35.

NIST: Call for proposals (2018). https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Post-Quantum-Cryptography-Standardization/Call-for-Proposals

36.

NIST: Round 1 submissions (2018). https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions

37.

Ourivski, A.V., Johansson, T.: New technique for decoding codes in the rank metric and its cryptography applications. Prob. Inf. Trans. 38(3), 237–246 (2002)CrossRef

38.

Phesso, A., Tillich, J.-P.: An efficient attack on a code-based signature scheme. In: Takagi, T. (ed.) PQCrypto 2016. LNCS, vol. 9606, pp. 86–103. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29360-8_7CrossRef

39.

Roy, P.S., Xu, R., Fukushima, K., Kiyomoto, S., Morozov, K., Takagi, T.: Supporting documentation of RaCoSS, post-Quantum Cryptography, Round 1 Submissions (2017). https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions

40.

Sendrier, N.: Code-based cryptography: state of the art and perspectives. IEEE Secur. Priv. 15(4), 44–50 (2017)CrossRef

41.

Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)MathSciNetCrossRef

42.

Stern, J.: A method for finding codewords of small weight. In: Cohen, G., Wolfmann, J. (eds.) Coding Theory 1988. LNCS, vol. 388, pp. 106–113. Springer, Heidelberg (1989). https://doi.org/10.1007/BFb0019850CrossRef

43.

Stern, J.: A new identification scheme based on syndrome decoding. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 13–21. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48329-2_2CrossRef

44.

Umana, V.G., Leander, G.: Practical key recovery attacks on two McEliece variants. In: International Conference on Symbolic Computation and Cryptography-SCC, vol. 2010, p. 62 (2010)

45.

Unruh, D.: Non-interactive zero-knowledge proofs in the quantum random oracle model. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 755–784. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_25CrossRefMATH

46.

Unruh, D.: Post-quantum security of Fiat-Shamir. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 65–95. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_3CrossRef

47.

Levy-dit Vehel, F., Perret, L.: Algebraic decoding of rank metric codes. In: Proceedings of YACC (2006)

48.

Véron, P.: Improved identification schemes based on error-correcting codes. Appl. Algebra Eng. Commun. Comput. 8(1), 57–69 (1997)MathSciNetCrossRef

49.

Wachter-Zeh, A.: Decoding of block and convolutional codes in rank metric. Ph.D. thesis, Universität Ulm (2013)

Title: Code-Based Signature Schemes from Identification Protocols in the Rank Metric
Authors: Emanuele Bellini
Florian Caullery
Alexandros Hasikos
Marcos Manzano
Victor Mateu
Publisher: Springer International Publishing
Book: Cryptology and Network Security
Print ISBN: 978-3-030-00433-0

Electronic ISBN: 978-3-030-00434-7

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-030-00434-7_14

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner