Towards the security of McEliece's cryptosystem based on Hermitian subfield subcodes | Applied Discrete Mathematics. Supplement. 2021. № 14. DOI: 10.17223/2226308X/14/39

Towards the security of McEliece's cryptosystem based on Hermitian subfield subcodes

The purpose of this paper is to provide a comprehensive security analysis for the parameter selection process, which involves the computational cost of the information set decoding (ISD) algorithm using Hermitian subfield subcode parameters.

Download file

Counter downloads: 25

Keywords

code-based cryptography, McEliece Cryptosystem, Hermitian subfield subcodes, Schur square dimension

Authors

Name	Organization	E-mail
Nagy G. P.	Budapest University of Technical and Economic Sciences	nagygp@math.bme.hu
El Khalfaoui S.	Boyai Institute of Szeged University	sabiraelkhalfaoui@gmail.com

Всего: 2

References

Wieschebrink C. Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes. Intern. Workshop Post-Quantum Cryptogr., Berlin, Springer, 2010, pp. 61-72.

Couvreur A., Otmani A., and Tillich J.-P. Polynomial time attack on wild mceliece over quadratic extensions. IEEE Trans. Inform. Theory, 2016, vol. 63(1), pp. 404-427.

Couvreur A., Marquez-Corbella I., and Pellikaan R. Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes. Coding Theory and Applications. Cham, Springer, 2015, pp. 133-140.

Couvreur A., Marquez-Corbella I., and Pellikaan R. Cryptanalysis of McEliece cryptosystem based on algebraic geometry codes and their subcodes. IEEE Trans. Inform. Theory, 2017, vol. 63(8), pp. 5404-5418.

Hoholdt T., and Pellikaan R. On the decoding of algebraic-geometric codes. Special Issue on Algebraic Geometry Codes. IEEE Trans. Inform. Theory, 1995, vol. 41, no. 6, part 1, pp. 1589-1614.

Post-Quantum Cryptography. http://csrc.nist.gov/projects/post-quantum-crypto graphy. Updated: March 25, 2020.

McEliece R. J. A Public-Key Cryptosystem Based on Algebraic Coding Theory. Jet Propulsion Lab, 1978. DSN Progress Report 44. pp. 114-116.

Shor P. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 1997, vol. 26, pp. 1484-1509.

Arute F., Arya K., Babbush R, et al. Quantum supremacy using a programmable superconducting processor. Nature, 2019, vol. 574(7779), pp. 505-510.

Berger T. P. and Loidreau P. How to mask the structure of codes for a cryptographic use. Des. Codes Cryptogr., 2005, vol. 35(1), pp. 63-79.

Couvreur A., Gaborit P., Gauthier-Umana V., et al. Distinguisher-based attacks on publickey cryptosystems using Reed -- Solomon codes. Des. Codes Cryptogr., 2014, vol. 73(2), pp. 641-666.

Berlekamp E. R., McEliece R. J., and van Tilborg H. C. A. On the inherent intractability of certain coding problems. IEEE Trans. Inform. Theory, 1978, vol. IT-24(3), pp. 384-386.

Prange E. The use of information sets in decoding cyclic codes. IRE Trans. Inform. Theory, 1962, vol. 8(5), pp. 5-9.

Canto Torres R. and Sendrier N. Analysis of information set decoding for a sub-linear error weight. LNCS, 2016, vol. 9606,pp. 144-161.

Cascudo I., Cramer R., Mirandola D., and Zemor G. Squares of random linear codes. IEEE Trans. Inform. Theory, 2015, vol. 61(3), pp. 1159-1173.

Stichtenoth H. Algebraic Function Fields and Codes. Graduate Texts in Math., Berlin, Springer Verlag, 2009, vol. 254, 355 p.

Mumford D. Varieties defined by quadratic equations. Questions on Algebraic Varieties. C.I.M.E. Summer Schools, vol. 51. Berlin; Heidelberg, Springer, 2010, pp. 29-100.

Menezes A. J., Blake I. F., Gao X., et al. Applications of Finite Fields. Kluwer Intern. Series Engin. Computer Sci., Boston, MA, Kluwer Academic Publishers, 1993, vol. 199. 218 p.

Xing C. P. and Stichtenoth H. The genus of maximal function fields over finite fields. Manuscripta Math., 1995, vol. 86(2), pp. 217-224.

El Khalfaoui S. and Nagy G. P. On the dimension of the subfield subcodes of 1-point Hermitian codes. Adv. Math. Commun., 2021, vol. 15(2), pp. 219-226.

Nagy G.P. and Khalfaoui S.E. Estimating the dimension of the subfield subcodes of Hermitian codes. Acta Cybernetica, 2020, vol. 24(4), pp. 625-641.

Baldi M., Barenghi A., Chiaraluce F., et al. A finite regime analysis of information set decoding algorithms. Algorithms, 2019, vol. 12(10), p. 209.