Randomized symmetric McEliece cryptosystem based on generalized Reed-Solomon codes
DOI:
https://doi.org/10.30837/rt.2020.1.200.03Keywords:
post-quantum cryptography, code-based cryptosystem, McEliece cryptosystem, generalized Reed-Solomon code, LPN-C cryptosystem, system of noised linear equationsAbstract
One of the actual problems of modern cryptography is the design of practical post-quantum cryptosystems whose security is based on the complexity of solving one computationally challenging problem, in the same way as the security of the RSA cryptosystem is based on the complexity of integer factorization. A promising class of such cryptosystems is formed by code-based cryptosystems the first asymmetric of which is the McEliece cryptosystem. The purpose of this work is to design and research a symmetric version of the McEliece cryptosystem based on generalized Reed-Solomon codes. These codes were chosen because they exist for all natural values of the parameters (the length and dimension of the code) and they are maximal distance separable allowing a wide range to change the characteristics of the relevant cryptosystems. In addition, very fast decoding algorithms are known for these codes. Asymmetric cryptosystems based on the generalized Reed-Solomon codes are not secure because for them there are efficient algorithms for recovering private keys from public keys.
A symmetric code cryptosystem is proposed that is more efficient (in terms of the length of the secret key for given security requirements) compared to the LPN-C cryptosystem. An estimate of the security of the proposed cryptosystem relative to an attack with the chosen plaintext is obtained and an algorithm for selecting parameters for constructing this cryptosystem is proposed. The proposed cryptosystem is compared with the LPN-C cryptosystem along the key length for a given lower limit of security to the attack in question.
References
McEliece R.J. A public-key cryptosystem based on algebraic coding theory // Prog. Rep., Jet Prop. Lab., California Inst. Technol, 1978. P. 114 – 116.
Jordan J.P. A variant of public-key cryptosystem based on Goppa codes // Sigact news, 1983. P. 61 – 66.
Rao T.R.N. Cryptosystems using algebraic codes // Int. Conf on Computer Systems & Signal Processing, 1984.
Rao T.R.N. Private-key algebraic code encryption / T.R.N. Rao, K.H. Nam // IEEE Trans. on Inform Theory, 1987. P. 829 – 833.
Sobhi Afshar A.A. Efficient secure channel coding based on quasy-ciclic low-density parity-check codes / A.A. Sobhi Afshar, T. Eghlidos, M.R. Aref // Journal of IET-Communications, 2009. P. 279 – 292.
Hooshmand R. Improving the Rao-Nam secret key cryptosystem using regular EDF-QC-LDPC codes / R. Hooshmand, T. Eghlidos, M.R. Aref // ISC Journal of Information sequrity, 2012. P. 3 – 14.
Nojima R. Semantic security for the McElice cryptosystem without random oracles / R. Nojima, H. Imai, K. Kobara, K. Morozov // Des. Codes Cryptography, 2008. P. 289 – 305.
Gilbert H. How to Encrypt with the LPN Problem / Н. Gilbert, J.B. Mattew, M.J.B. Robshaw, Y. Seurin // ICALP (2), Proceedings, Springer Verlag, 2008. P. 679- 690.
Федоренко С.В. Методы быстрого декодирования линейных блоковых кодов. С.-Петербург : ГУАПб, 2008. 199 с.
Niederreiter N. Knapsack-type cryptosystems and algebraic coding theory // Problems of Control and Information Theory, 1986. P. 159 – 166.
Berger T. How to mask the structure of codes for a cryptographic use / T. Berger, P. Loidreau // Designs, Codes and Cryptography, 2005. P. 63.
Сидельников В.М. О системе шифрования, построенной на основе обобщенных кодов Рида-Соломона / В.М. Сидельников, С.О. Шестаков // Дискретная математика, 1992. Т. 4. Вып. 3. С. 57 – 63.
Wieschebrink Ch. Cryptanalysis of the Niederreiters public key scheme based on GRS sub-codes // Post-Quantum Cryptography, 2010 Proceedings. Springer Verlag, 2010. P. 61 – 72.
Мак-Вильямс Ф.Дж. Теория кодов, исправляющих ошибки ; пер. с англ. / Ф.Дж. Мак-Вильямс, Н. Дж. А. Слоэн. Москва : Связь, 1979. 743 с.
Hoeffding W. Probability inequalities for sums of bounded random variables // J. Amer. Statist. Assoc, 1963. Vol. 58. № 301. P. 13 – 30.
Алексейчук А. Н. Метод восстановления систематических линейных кодов по наборам искаженных кодовых слов / А.Н. Алексейчук, А.Ю. Грязнухин // Прикладная радиоэлектроника. 2013. Т. 12. № 2. С. 313 – 318.
Zhang B. Fast correlation attacks over extension fields, large-unit linear approximation and cryptanalysis of SNOW 2.0 / B. Zhang, C. Xu, W. // Meier–Cryptology ePrint Archive, 2016/311. http://eprint.iacr.org/2016/311.
Wagner D. A generalized birthday problem // Advances in Cryptology – CRYPTO’02, Proceedings. Springer Verlag, 2002. P. 288 – 303.
Downloads
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
