Abstract
In this paper we survey new results for rank-based cryptography: cryptosystems which are based on error-correcting codes embedded with the rank metric. These new results results first concern the LRPC cryptosystem, a cryptosystem based on a new class of decodable rank codes: the LRPC codes (for Low Rank Parity Check codes) which can be seen as an analog of the classical LDPC codes but for rank metric. The LRPC cryptosystem can benefit from very small public keys of less than 2,000 bits and is moreover very fast. We also present new optimized attacks for solving the general case of the rank syndrome decoding problem, together with a zero-knowledge authentication scheme and a new signature scheme based on a mixed errors-erasures decoding of LRPC codes, both these systems having public keys of a few thousand bits. These new recent results highlight that rank-based cryptography has many good features that can be used for practical cryptosystems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aguilar, C., Gaborit, P., Schrek, J.: A new zero-knowledge code based identification scheme with reduced communication. In: 2011 IEEE Information Theory Workshop (ITW), pp. 648–652 (2011)
Barbulescu, R., Gaudry, P., Joux, A., Thomé, E.: A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, eprint iacr 2013/400
Becker, A., Joux, A., May, A., Meurer, A.: Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 520–536. Springer, Heidelberg (2012)
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)
Berger, T., Loidreau, P.: Designing an Efficient and Secure Public-Key Cryptosystem Based on Reducible Rank Codes. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 218–229. Springer, Heidelberg (2004)
Chabaud, F., Stern, J.: The Cryptographic Security of the Syndrome in Decoding Problem for Rank Distance Codes. In: Kim, K.-C., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 368–381. Springer, Heidelberg (1996)
Chen, K.: A New Identification Algorithm. In: Dawson, E., Golić, J. (eds.) Cryptography: Policy and Algorithms 1995. LNCS, vol. 1029, pp. 244–249. Springer, Heidelberg (1996)
Courtois, N.T., Finiasz, M., Sendrier, N.: How to achieve a Mc-Eliece-based digital signature scheme. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 157–174. Springer, Heidelberg (2001)
Faugère, J.-C., Levy-dit-Vehel, F., Perret, L.: Cryptanalysis of MinRank. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 280–296. Springer, Heidelberg (2008)
Faugère, J.-C., El Din, M.S., Spaenlehauer, P.-J.: Computing loci of rank defects of linear matrices using Grbner bases and applications to cryptology. In: ISSAC 2010, pp. 257–264 (2010)
Faure, C., Loidreau, P.: A New Public-Key Cryptosystem Based on the Problem of Reconstructing p-Polynomials. In: Ytrehus, Ø. (ed.) WCC 2005. LNCS, vol. 3969, pp. 304–315. Springer, Heidelberg (2006)
Gabidulin, E.M.: Theory of Codes with Maximum Rank Distance. Probl. Peredachi Inf. (21), 3–16 (1985)
Gabidulin, E.M., Paramonov, A.V., Tretjakov, O.V.: Ideals over a Non-Commutative Ring and their Applications in Cryptology. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 482–489. Springer, Heidelberg (1991)
Gaborit, P., Murat, G., Ruatta, O., Zémor, G.: Low Rank Parity Check Codes and their application in cryptography. In: The Preproceedings of Workshop on Coding and Cryptography (WCC) 2013, Borgen, Norway, pp. 167–179 (2013)
Gaborit, P., Ruatta, O., Schrek, J., Zémor, G.: RankSign: An efficient signature algorithm based on the rank metric. eprint iacr (submitted)
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)
Gaborit, P., Ruatta, O., Schrek, J.: On the complexity of the rank syndrome decoding problem. eprint. Submitted to IEEE Trans. Information Theory
von zur Gathen, J., Gerhard, J.: Modern computer algebra. Cambridge University Press (2003)
Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A Ring-Based Public Key Cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998)
Levy-dit-Vehel, F., Perret, L.: Algebraic decoding of rank metric codes. In: Proceedings of YACC 2006 (2006)
Loidreau, P.: Designing a Rank Metric Based McEliece Cryptosystem. In: Sendrier, N. (ed.) PQCrypto 2010. LNCS, vol. 6061, pp. 142–152. Springer, Heidelberg (2010)
Loidreau, P.: Properties of codes in rank metric, http://arxiv.org/abs/cs/0610057
Misoczki, R., Tillich, J.-P., Sendrier, N., Barreto, P.S.L.M.: MDPC-McEliece: New McEliece Variants from Moderate Density Parity-Check Codes. Cryptology ePrint Archive: Report 2012/409
Ore, O.: On a special class of polynomials. Trans. American Math. Soc. (1933)
Ourivski, A.V., Johansson, T.: New Technique for Decoding Codes in the Rank Metric and Its Cryptography Applications. Probl. Inf. Transm. (38), 237–246 (2002)
Overbeck, R.: Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes. J. Cryptology 21(2), 280–301 (2008)
Stern, J.: A new paradigm for public key identification. IEEE Transactions on Information Theory 42(6), 2757–2768 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Gaborit, P., Ruatta, O., Schrek, J., Zémor, G. (2014). New Results for Rank-Based Cryptography. In: Pointcheval, D., Vergnaud, D. (eds) Progress in Cryptology – AFRICACRYPT 2014. AFRICACRYPT 2014. Lecture Notes in Computer Science, vol 8469. Springer, Cham. https://doi.org/10.1007/978-3-319-06734-6_1
Download citation
DOI: https://doi.org/10.1007/978-3-319-06734-6_1
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06733-9
Online ISBN: 978-3-319-06734-6
eBook Packages: Computer ScienceComputer Science (R0)