nach oben

Designs, Codes and Cryptography

Erschienen in:

02.07.2019

New rank codes based encryption scheme using partial circulant matrices

verfasst von: Terry Shue Chien Lau, Chik How Tan

Erschienen in: Designs, Codes and Cryptography | Ausgabe 12/2019

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We propose a new rank metric code based encryption based on the hard problem of rank syndrome decoding problem. We consider a generator matrix for Gabidulin codes in the form of k-partial circulant matrix. We distort the matrix G by adding it with another random k-partial circulant matrix and multiplying the product with a random circulant matrix. We also convert our encryption into an IND-CCA2 secured encryption scheme under assumption of Rank Syndrome Decoding problem. Our encryption has the smallest key size (of 4.306 KB) at 256-bit security level as compared to all the other rank code based encryption schemes with zero decryption failure and hidden structure for the decodable codes.

Vorheriger Artikel On the geometry of full points of abstract unitals

Nächster Artikel More accurate results on the provable security of AES against impossible differential cryptanalysis

Aguilar C., Blazy O., Deneuville J., Gaborit P., Zémore G.: Effcient encryption from random quasi-cyclic codes. IEEE Trans. Inf. Theory 64(5), 3927–3943 (2018).CrossRef

Aragon A., Gaborit P., Hauteville A., Tillich J.-P.: A new algorithm for solving the rank syndrome decoding problem. In: Proceedings of IEEE International Symposium on Information Theory (ISIT 2018), pp. 2421–2425 (2018).

Bellare M., Rogaway P.: Optimal asymmetric encryption. In: Proceedings of the 13th Annual International Conference on Theory and Application of Cryptographic Techniques (EUROCRYPT 1994), pp. 92–111 (1995).CrossRef

Berger, T., Loidreau, P.: Designing an efficient and secure public-key cryptosystem based on reducible rank codes. In: Proceedings of Progress in Cryptology (INDOCRYPT 2004), pp. 218–229 (2004).CrossRef

Berlekamp E., McEliece R., Tilborg H.V.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24(3), 384–386 (1978).MathSciNetCrossRef

Chalkley R.: Circulant matrices and algebraic equations. Math. Mag. 48(2), 73–80 (1975).MathSciNetCrossRef

Faugère J.-C., Levy-dit-Vehel F., Perret L.: Cryptanalysis of MinRank. In: Proceedings of Advances in Cryptology (CRYPTO 2008), pp. 280–296 (2008).

Fujisaki E., Okamoto T.: Secure integration of asymmetric and symmetric encryption schemes. In: Proceedings of Advances in Cryptology (CRYPTO 1999), pp. 535–554 (1999).CrossRef

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

10.

Gabidulin E.M., Loidreau P.: Subfield subcodes of maximal rank distance codes. In: Proceedings of 7th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT 2000), pp. 151–156 (2000).

11.

Gabidulin E.M., Ourivski A.V.: Modified GPT PKC with right scrambler. Electron. Notes Discret. Math. 6, 168–177 (2001).MathSciNetCrossRef

12.

Gabidulin E.M., Paramonov A.V., Tretjakov O.V.: Ideals over a non-commutative ring and their application in cryptology. In: Proceedings of the 10th Annual International Conference on Theory and Application of Cryptographic Techniques (EUROCRYPT 1991), pp. 482–489 (1991).

13.

Gabidulin E.M., Ourivski A.V., Honary B., Ammar B.: Reducible rank codes and their applications to cryptography. IEEE Trans. Inf. Theory 49(12), 3289–3293 (2003).MathSciNetCrossRef

14.

Gabidulin E.M., Rashwan H., Honary B.: On improving security of GPT cryptosystems. In: Proceedings of IEEE International Symposium on Information Theory (ISIT 2009), pp. 1110–1114 (2009).

15.

Gaborit P., Ruatta O., Schrek J., Zémor G.: New results for rank-based cryptography. In: Proceedings of Progress in Cryptology (AFRICACRYPT 2014), pp. 1–12 (2014).

16.

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

17.

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

18.

Gaborit P., Hauteville A., Phan D.H., Tillich J.-P.: Identity-based encryption from codes with Rank Metric. In: Proceedings of Advances in Cryptology (CRYPTO 2017), pp. 194–224 (2017).CrossRef

19.

Galvez L., Kim J., Kim M.J., Kim Y., Lee N.: McNie: compact McEliece-Niederreiter cryptosystem. https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/McNie.zip (2017). Accessed 27 Feb 2018.

20.

Gibson J.K.: Severely denting the Gabidulin version of the McEliece public-key cryptosystem. Des. Codes Cryptogr. 6, 37–45 (1995).MathSciNetCrossRef

21.

Goubin L., Courtois N.T.: Cryptanalysis of the TTM cryptosystem. In: Proceedings of Advances in Cryptology (ASIACRYPT 2000), pp. 44–57 (2000).CrossRef

22.

Hauteville A., Tillich J.-P.: New algorithms for decoding in the rank metric and an attack on the LRPC cryptosystem. In: Proceedings of IEEE International Symposium on Information (ISIT 2015), pp. 2747–2751 (2015).

23.

Horlemann-Trautmann A., Marshall K.: New criteria for MRD and Gabidulin codes and some rank-metric code constructions. Adv. Math. Commun. 11(3), 533–548 (2017).MathSciNetCrossRef

24.

Horlemann-Trautmann A., Marshall K., Rosenthal J.: Extension of overbeck’s attack for Gabidulin based cryptosystems. Des. Codes Cryptogr. 86(2), 319–340 (2018).MathSciNetCrossRef

25.

Kobara K., Imai H.: Semantically secure McEliece public-key cryptosystems-conversions for McEliece PKC. In: Proceedings of Public-Key Cryptography (PKC 2001), pp. 19–35 (2001).CrossRef

26.

Lau T.S.C., Tan C.H.: A new technique in rank metric code-based encryption. Cryptography 2(4), 32 (2018).CrossRef

27.

Lau T.S.C., Tan C.H.: Key recovery attack on McNie based on low rank parity check codes and its reparation. In: Proceedings of Advances in Information and Computer Security (IWSEC 2018), pp. 19–34 (2018).CrossRef

28.

Levy-dit-Vehel F., Perret L.: Algebraic decoding of rank metric codes. In: Proceedings of Yet Another Conference on Cryptography (YACC 2006), pp. 142–152 (2006).

29.

Loidreau P.: Designing a rank metric based McEliece cryptosystem. In: Proceedings of the Third International Conference on Post-Quantum Cryptography (PQCrypto 2010), pp. 142–152 (2010).CrossRef

30.

Loidreau P.: A new rank metric codes based encryption scheme. In: Proceedings of the 8th International Conference on Post-Quantum Cryptography (PQCrypto 2017), pp. 3–17 (2017).CrossRef

31.

McEliece R.J.: A public-key cryptosystem based on algebraic coding theory. The Deep Space Network Progress Report 42-44, Jet Propulsion Laboratory, pp. 114–116 (1978).

32.

Misoczki R., Tillich J.-P., Sendrier N., Barreto P.S.L.M.: MDPC-McEliece: new McEliece variants from moderate density parity-check codes. In: Proceedings of IEEE International Symposium on Information Theory (ISIT 2013), pp. 2069–2073 (2013).

33.

Ore O.: On a special class of polynomials. Trans. Am. Math. Soc. 35(3), 559–584 (1933).MathSciNetCrossRef

34.

Otmani A., Kalachi H.T., Ndjeya S.: Improved cryptanalysis of rank metric schemes based on Gabidulin codes. Des. Codes Cryptogr. 86(9), 1983–1996 (2018).MathSciNetCrossRef

35.

Ourivski A.V., Gabidulin E.M.: Column scrambler for the GPT cryptosystem. Discret. Appl. Math. 128, 207–221 (2003).MathSciNetCrossRef

36.

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

37.

Overbeck R.: Structural attacks for public key cryptosystems based on Gabidulin codes. J. Cryptol. 21(2), 280–301 (2008).MathSciNetCrossRef

38.

Pointcheval D.: Chosen-ciphertext security for any one-way cryptosystem. In: Proceedings of Public Key Cryptography (PKC 2000), pp. 129–146 (2000).CrossRef

39.

Rashwan H., Gabidulin E.M., Honary B.: A smart approach for GPT cryptosystem based on rank codes. In: Proceedings of IEEE International Symposium on Information Theory (ISIT 2010), pp. 2463–2467 (2010).

40.

Wachter-Zeh A., Afanassiev V., Sidorenko V.: Fast decoding of Gabidulin codes. Des. Codes Cryptogr. 66, 57–73 (2013).MathSciNetCrossRef

Titel: New rank codes based encryption scheme using partial circulant matrices
verfasst von: Terry Shue Chien Lau
Chik How Tan
Publikationsdatum: 02.07.2019
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 12/2019
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-019-00659-0

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 12/2019

On the geometry of full points of abstract unitals

Necessary field size and probability for MDP and complete MDP convolutional codes

Steiner systems and 2-designs from ternary linear codes of length

Construction of resilient Boolean functions in odd variables with strictly almost optimal nonlinearity

Multidimensional quasi-twisted codes: equivalent characterizations and their relation to multidimensional convolutional codes

Constructions and uses of incomplete pairwise balanced designs