Encryption scheme based on expanded Reed-Solomon codes

Karan Khathuria; Joachim Rosenthal; Violetta Weger

doi:10.3934/amc.2020053

Previous Article
On the dimension of the subfield subcodes of 1-point Hermitian codes
AMC Home
This Issue
Next Article

May 2021, 15(2): 207-218. doi: 10.3934/amc.2020053

Encryption scheme based on expanded Reed-Solomon codes

Karan Khathuria , Joachim Rosenthal and Violetta Weger

Institute of Mathematics, University of Zurich, Winterthurerstrasse 190, 8057 Zurich, Switzerland

Received June 2019 Revised October 2019 Published January 2020

We present a code-based public-key cryptosystem, in which we use Reed-Solomon codes over an extension field as secret codes and disguise it by considering its shortened expanded code over the base field. Considering shortened expanded codes provides a safeguard against distinguisher attacks based on the Schur product. Moreover, without using a cyclic or a quasi-cyclic structure we obtain a key size reduction of nearly $ 45 \% $ compared to the classic {McE}liece cryptosystem proposed by Bernstein et al.

Keywords: Code-based cryptography, McEliece cryptosystem, Reed-Solomon codes, expanded codes, shortened codes.

Mathematics Subject Classification: 14G50, 94A60, 11T71.

Citation: Karan Khathuria, Joachim Rosenthal, Violetta Weger. Encryption scheme based on expanded Reed-Solomon codes. Advances in Mathematics of Communications, 2021, 15 (2) : 207-218. doi: 10.3934/amc.2020053

References:

[1]	C. Aguilar-Melchor, O. Blazy, J.-C. Deneuville, P. Gaborit and G. Zémor, Efficient encryption from random quasi-cyclic codes, IEEE Transactions on Information Theory, 64 (2018), 3927-3943. doi: 10.1109/TIT.2018.2804444. Google Scholar
[2]	M. Albrecht, C. Cid, K. G. Paterson, C. J. Tjhai and M. Tomlinson, NTS-KEM, 2018. Google Scholar
[3]	N. Aragon, P. S. L. M. Barreto, S. Bettaieb, Lo. Bidoux, O. Blazy, J.-C. Deneuville, P. Gaborit, S. Gueron, T. Guneysu, C. A. Melchor, R. Misoczki, E. Persichetti, N. Sendrier, J.-P. Tillich and G. Zémor, Bike: Bit Flipping Key Encapsulation, 2017. Google Scholar
[4]	M. Baldi, A. Barenghi, F. Chiaraluce, G. Pelosi and P. Santini, LEDAkem: A post-quantum key encapsulation mechanism based on QC-LDPC codes, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Cham, 10786 (2018), 3-24. Google Scholar
[5]	M. Baldi, M. Bianchi, F. Chiaraluce, J. Rosenthal and D. Schipani, A variant of the McEliece cryptosystem with increased public key security, Proceedings of the Seventh International Workshop on Coding and Cryptography (WCC) 2011, (2011), 173–182. Google Scholar
[6]	M. Baldi, M. Bianchi, F. Chiaraluce, J. Rosenthal and D. Schipani, Method and Apparatus for Public-Key Cryptography Based on Error Correcting Codes, 2015, US Patent 9,191,199. Google Scholar
[7]	M. Baldi, M. Bodrato and F. Chiaraluce, A new analysis of the McEliece cryptosystem based on QC-LDPC codes, International Conference on Security and Cryptography for Networks, Springer Berlin Heidelberg, (2008), 246–262. Google Scholar
[8]	M. Baldi, F. Chiaraluce, J. Rosenthal, P. Santini and D. Schipani, On the security of generalized Reed-Solomon code-based cryptosystems, IET Information Security, (2019). Google Scholar
[9]	A. Becker, A. Joux, A. May and A. Meurer, Decoding random binary linear codes in $2^{n/20}$: How $1+ 1 = 0$ improves information set decoding, Advances in Cryptology—EUROCRYPT 2012, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7237 (2012), 520-536. doi: 10.1007/978-3-642-29011-4_31. Google Scholar
[10]	T. P. Berger and P. Loidreau, How to mask the structure of codes for a cryptographic use, Des. Codes Cryptogr., 35 (2005), 63-79. doi: 10.1007/s10623-003-6151-2. Google Scholar
[11]	D. J. Bernstein, T. Lange and C. Peters, Attacking and defending the McEliece cryptosystem, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 5299 (2008), 31-46. doi: 10.1007/978-3-540-88403-3_3. Google Scholar
[12]	D. J. Bernstein, T. Lange and C. Peters, Wild McEliece, Selected Areas in Cryptography, Lecture Notes in Comput. Sci., Springer, Heidelberg, 6544 (2011), 143-158. doi: 10.1007/978-3-642-19574-7_10. Google Scholar
[13]	D. J. Bernstein, T. Lange and C. Peters, Smaller decoding exponents: Ball-collision decoding, Advances in Cryptology—CRYPTO 2011, Lecture Notes in Comput. Sci., Springer, Heidelberg, 6841 (2011), 743-760. doi: 10.1007/978-3-642-22792-9_42. Google Scholar
[14]	J. Bolkema, H. Gluesing-Luerssen, C. A. Kelley, K. E. Lauter, B. Malmskog and J. Rosenthal, Variations of the McEliece cryptosystem, Algebraic Geometry for Coding Theory and Cryptography, Assoc. Women Math. Ser., Springer, Cham, 9 (2017), 129-150. Google Scholar
[15]	A. Couvreur, P. Gaborit, V. Gauthier-Umaña, A. Otmani and J.-P. Tillich, Distinguisher-based attacks on public-key cryptosystems using reed-solomon codes, Designs, Codes and Cryptography, 73 (2014), 641-666. doi: 10.1007/s10623-014-9967-z. Google Scholar
[16]	A. Couvreur, I. Márquez-Corbella and R. Pellikaan, Cryptanalysis of McEliece cryptosystem based on algebraic geometry codes and their subcodes, IEEE Trans. Inform. Theory, 63 (2017), 5404-5418. doi: 10.1109/TIT.2017.2712636. Google Scholar
[17]	A. Couvreur, A. Otmani and J.-P. Tillich, Polynomial time attack on wild McEliece over quadratic extensions, IEEE Transactions on Information Theory, 63 (2017), 404-427. doi: 10.1109/TIT.2016.2574841. Google Scholar
[18]	A. Couvreur, A. Otmani, J.-P. Tillich and V. Gauthier-Umaña, A polynomial-time attack on the BBCRS scheme, Public-key Cryptography-PKC 2015, Lecture Notes in Comput. Sci., Springer, Heidelberg, 9020 (2015), 175–193. doi: 10.1007/978-3-662-46447-2_8. Google Scholar
[19]	J.-C. Faugère, V. Gauthier-Umaña, A. Otmani, L. Perret and J.-P. Tillich, A distinguisher for high-rate McEliece cryptosystems, IEEE Transactions on Information Theory, 59 (2013), 6830-6844. doi: 10.1109/TIT.2013.2272036. Google Scholar
[20]	V. Gauthier-Umaña, A. Otmani and J.-P. Tillich, A distinguisher-based attack on a variant of McEliece's cryptosystem based on reed-solomon codes, Preprint, (2012), arXiv: 1204.6459. Google Scholar
[21]	C. T. Gueye, J. B. Klamti and S. Hirose, Generalization of BJMM-ISD using May-Ozerov nearest neighbor algorithm over an arbitrary finite field $\mathbb{F}_q$, Codes, Cryptology and Information Security, Lecture Notes in Comput. Sci., Springer, Cham, 10194 (2017), 96-109. Google Scholar
[22]	S. Hirose, May-Ozerov algorithm for nearest-neighbor problem over $\mathbb{F}_q$ and its application to information set decoding, International Conference for Information Technology and Communications, Springer, (2016), 115–126. Google Scholar
[23]	C. Interlando, K. Khathuria, N. Rohrer, J. Rosenthal and V. Weger, Generalization of the ball-collision algorithm, Preprint, (2018), arXiv: 1812.10955. Google Scholar
[24]	H. Janwa and O. Moreno, McEliece public key cryptosystems using algebraic-geometric codes, Designs, Codes and Cryptography, 8 (1996), 293-307. doi: 10.1023/A:1027351723034. Google Scholar
[25]	K. Khathuria, J. Rosenthal and V. Weger, Weight two masking of the reed-solomon structure in conjugation with list decoding, Proceedings of 23rd International Symposium on Mathematical Theory of Networks and Systems, Hong Kong University of Science and Technology, Hong Kong, (2018), 309–314. Google Scholar
[26]	G. Landais and J.-P. Tillich, An efficient attack of a McEliece cryptosystem variant based on convolutional codes, International Workshop on Post-Quantum Cryptography, Springer, (2013), 102–117. Google Scholar
[27]	P. J. Lee and E. F. Brickell, An observation on the security of McEliece's public-key cryptosystem, Advances in Cryptology—EUROCRYPT '88 (Davos, 1988), Lecture Notes in Comput. Sci., Springer, Berlin, 330 (1988), 275-280. doi: 10.1007/3-540-45961-8_25. Google Scholar
[28]	J. S. Leon, A probabilistic algorithm for computing minimum weights of large error-correcting codes. Coding techniques and coding theory, IEEE Transactions on Information Theory, 34 (1988), 1354-1359. doi: 10.1109/18.21270. Google Scholar
[29]	C. Löndahl and T. Johansson, A new version of McEliece PKC based on convolutional codes, International Conference on Information and Communications Security, Springer, (2012), 461–470. Google Scholar
[30]	A. May and I. Ozerov, On computing nearest neighbors with applications to decoding of binary linear codes, Advances in Cryptology—EUROCRYPT 2015. Part Ⅰ, Lecture Notes in Comput. Sci., Springer, Heidelberg, 9056 (2015), 203-228. doi: 10.1007/978-3-662-46800-5_9. Google Scholar
[31]	R. J. McEliece, A Public-Key Cryptosystem Based on Algebraic Coding Theory, Technical report, DSN Progress report, Jet Propulsion Laboratory, Pasadena, 1978. Google Scholar
[32]	C. A. Melchor, N. Aragon, M. Bardet, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville, P. Gaborit, A. Hauteville, A. Otmani, O. Ruatta, J.-P. Tillich and G. Zémor, ROLLO-Rank-Ouroboros, LAKE & LOCKER, 2018. Google Scholar
[33]	L. Minder and A. Shokrollahi, Cryptanalysis of the Sidelnikov cryptosystem, Advances in Cryptology—EUROCRYPT 2007, Lecture Notes in Comput. Sci., Springer, Berlin, 4515 (2007), 347-360. doi: 10.1007/978-3-540-72540-4_20. Google Scholar
[34]	R. Misoczki, J.-P. Tillich, N. Sendrier and P. S. L. M. Barreto, MDPC-McEliece: New McEliece variants from moderate density parity-check codes, 2013 IEEE International Symposium on Information Theory, (2013), 2069–2073. doi: 10.1109/ISIT.2013.6620590. Google Scholar
[35]	R. Niebuhr, E. Persichetti, P.-L. Cayrel, S. Bulygin and J. Buchmann, On lower bounds for information set decoding over $\mathbb{F}_q$ and on the effect of partial knowledge, Int. J. Inf. Coding Theory, 4 (2017), 47-78. doi: 10.1504/IJICOT.2017.081458. Google Scholar
[36]	H. Niederreiter, Knapsack-type cryptosystems and algebraic coding theory, Problems Control Inform. Theory/Problemy Upravlen. Teor. Inform., 15 (1986), 159-166. Google Scholar
[37]	A. Otmani, J.-P. Tillich and L. Dallot, Cryptanalysis of two McEliece cryptosystems based on quasi-cyclic codes, Mathematics in Computer Science, 3 (2010), 129-140. doi: 10.1007/s11786-009-0015-8. Google Scholar
[38]	C. Peters, Information-set decoding for linear codes over $\mathbb{F}_q$, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 6061 (2010), 81–94, https://bitbucket.org/cbcrypto/isdfq/src/master/. doi: 10.1007/978-3-642-12929-2_7. Google Scholar
[39]	E. Prange, The use of information sets in decoding cyclic codes, IRE Transactions on Information Theory, 8 (1962), S5–S9. doi: 10.1109/tit.1962.1057777. Google Scholar
[40]	P. W. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, 35th Annual Symposium on Foundations of Computer Science (Santa Fe, NM, 1994), IEEE Comput. Soc. Press, Los Alamitos, CA, (1994), 124–134. doi: 10.1109/SFCS.1994.365700. Google Scholar
[41]	V. M. Sidelnikov, A public key cryptosystem based on Reed-Muller binary codes, Discrete Math. Appl., 4 (1994), 191-207. doi: 10.1515/dma.1994.4.3.191. Google Scholar
[42]	V. M. Sidelnikov and S. O. Shestakov, On an encoding system constructed on the basis of generalized Reed-Solomon codes, Diskret. Mat., 4 (1992), 57-63. doi: 10.1515/dma.1992.2.4.439. Google Scholar
[43]	V. M. Sidelnikov and S. O. Shestakov, On insecurity of cryptosystems based on generalized Reed-Solomon codes, Discrete Mathematics and Applications, 2 (1992), 439-444. Google Scholar
[44]	J. Stern, A method for finding codewords of small weight, Coding Theory and Applications, Lecture Notes in Comput. Sci., Springer, New Yorkpages, 388 (1989), 106-113. doi: 10.1007/BFb0019850. Google Scholar
[45]	A. Vardy and Y. Be'ery, Bit-level soft-decision decoding of Reed-Solomon codes, IEEE Transactions on Communications, 39 (1991), 440-444. Google Scholar
[46]	C. Wieschebrink, Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 6061 (2010), 61-72. doi: 10.1007/978-3-642-12929-2_5. Google Scholar
[47]	Y. Q. Wu, On expanded cyclic and Reed-Solomon codes, IEEE Transactions on Information Theory, 57 (2011), 601-620. doi: 10.1109/TIT.2010.2095150. Google Scholar

show all references

References:

[1]	C. Aguilar-Melchor, O. Blazy, J.-C. Deneuville, P. Gaborit and G. Zémor, Efficient encryption from random quasi-cyclic codes, IEEE Transactions on Information Theory, 64 (2018), 3927-3943. doi: 10.1109/TIT.2018.2804444. Google Scholar
[2]	M. Albrecht, C. Cid, K. G. Paterson, C. J. Tjhai and M. Tomlinson, NTS-KEM, 2018. Google Scholar
[3]	N. Aragon, P. S. L. M. Barreto, S. Bettaieb, Lo. Bidoux, O. Blazy, J.-C. Deneuville, P. Gaborit, S. Gueron, T. Guneysu, C. A. Melchor, R. Misoczki, E. Persichetti, N. Sendrier, J.-P. Tillich and G. Zémor, Bike: Bit Flipping Key Encapsulation, 2017. Google Scholar
[4]	M. Baldi, A. Barenghi, F. Chiaraluce, G. Pelosi and P. Santini, LEDAkem: A post-quantum key encapsulation mechanism based on QC-LDPC codes, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Cham, 10786 (2018), 3-24. Google Scholar
[5]	M. Baldi, M. Bianchi, F. Chiaraluce, J. Rosenthal and D. Schipani, A variant of the McEliece cryptosystem with increased public key security, Proceedings of the Seventh International Workshop on Coding and Cryptography (WCC) 2011, (2011), 173–182. Google Scholar
[6]	M. Baldi, M. Bianchi, F. Chiaraluce, J. Rosenthal and D. Schipani, Method and Apparatus for Public-Key Cryptography Based on Error Correcting Codes, 2015, US Patent 9,191,199. Google Scholar
[7]	M. Baldi, M. Bodrato and F. Chiaraluce, A new analysis of the McEliece cryptosystem based on QC-LDPC codes, International Conference on Security and Cryptography for Networks, Springer Berlin Heidelberg, (2008), 246–262. Google Scholar
[8]	M. Baldi, F. Chiaraluce, J. Rosenthal, P. Santini and D. Schipani, On the security of generalized Reed-Solomon code-based cryptosystems, IET Information Security, (2019). Google Scholar
[9]	A. Becker, A. Joux, A. May and A. Meurer, Decoding random binary linear codes in $2^{n/20}$: How $1+ 1 = 0$ improves information set decoding, Advances in Cryptology—EUROCRYPT 2012, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7237 (2012), 520-536. doi: 10.1007/978-3-642-29011-4_31. Google Scholar
[10]	T. P. Berger and P. Loidreau, How to mask the structure of codes for a cryptographic use, Des. Codes Cryptogr., 35 (2005), 63-79. doi: 10.1007/s10623-003-6151-2. Google Scholar
[11]	D. J. Bernstein, T. Lange and C. Peters, Attacking and defending the McEliece cryptosystem, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 5299 (2008), 31-46. doi: 10.1007/978-3-540-88403-3_3. Google Scholar
[12]	D. J. Bernstein, T. Lange and C. Peters, Wild McEliece, Selected Areas in Cryptography, Lecture Notes in Comput. Sci., Springer, Heidelberg, 6544 (2011), 143-158. doi: 10.1007/978-3-642-19574-7_10. Google Scholar
[13]	D. J. Bernstein, T. Lange and C. Peters, Smaller decoding exponents: Ball-collision decoding, Advances in Cryptology—CRYPTO 2011, Lecture Notes in Comput. Sci., Springer, Heidelberg, 6841 (2011), 743-760. doi: 10.1007/978-3-642-22792-9_42. Google Scholar
[14]	J. Bolkema, H. Gluesing-Luerssen, C. A. Kelley, K. E. Lauter, B. Malmskog and J. Rosenthal, Variations of the McEliece cryptosystem, Algebraic Geometry for Coding Theory and Cryptography, Assoc. Women Math. Ser., Springer, Cham, 9 (2017), 129-150. Google Scholar
[15]	A. Couvreur, P. Gaborit, V. Gauthier-Umaña, A. Otmani and J.-P. Tillich, Distinguisher-based attacks on public-key cryptosystems using reed-solomon codes, Designs, Codes and Cryptography, 73 (2014), 641-666. doi: 10.1007/s10623-014-9967-z. Google Scholar
[16]	A. Couvreur, I. Márquez-Corbella and R. Pellikaan, Cryptanalysis of McEliece cryptosystem based on algebraic geometry codes and their subcodes, IEEE Trans. Inform. Theory, 63 (2017), 5404-5418. doi: 10.1109/TIT.2017.2712636. Google Scholar
[17]	A. Couvreur, A. Otmani and J.-P. Tillich, Polynomial time attack on wild McEliece over quadratic extensions, IEEE Transactions on Information Theory, 63 (2017), 404-427. doi: 10.1109/TIT.2016.2574841. Google Scholar
[18]	A. Couvreur, A. Otmani, J.-P. Tillich and V. Gauthier-Umaña, A polynomial-time attack on the BBCRS scheme, Public-key Cryptography-PKC 2015, Lecture Notes in Comput. Sci., Springer, Heidelberg, 9020 (2015), 175–193. doi: 10.1007/978-3-662-46447-2_8. Google Scholar
[19]	J.-C. Faugère, V. Gauthier-Umaña, A. Otmani, L. Perret and J.-P. Tillich, A distinguisher for high-rate McEliece cryptosystems, IEEE Transactions on Information Theory, 59 (2013), 6830-6844. doi: 10.1109/TIT.2013.2272036. Google Scholar
[20]	V. Gauthier-Umaña, A. Otmani and J.-P. Tillich, A distinguisher-based attack on a variant of McEliece's cryptosystem based on reed-solomon codes, Preprint, (2012), arXiv: 1204.6459. Google Scholar
[21]	C. T. Gueye, J. B. Klamti and S. Hirose, Generalization of BJMM-ISD using May-Ozerov nearest neighbor algorithm over an arbitrary finite field $\mathbb{F}_q$, Codes, Cryptology and Information Security, Lecture Notes in Comput. Sci., Springer, Cham, 10194 (2017), 96-109. Google Scholar
[22]	S. Hirose, May-Ozerov algorithm for nearest-neighbor problem over $\mathbb{F}_q$ and its application to information set decoding, International Conference for Information Technology and Communications, Springer, (2016), 115–126. Google Scholar
[23]	C. Interlando, K. Khathuria, N. Rohrer, J. Rosenthal and V. Weger, Generalization of the ball-collision algorithm, Preprint, (2018), arXiv: 1812.10955. Google Scholar
[24]	H. Janwa and O. Moreno, McEliece public key cryptosystems using algebraic-geometric codes, Designs, Codes and Cryptography, 8 (1996), 293-307. doi: 10.1023/A:1027351723034. Google Scholar
[25]	K. Khathuria, J. Rosenthal and V. Weger, Weight two masking of the reed-solomon structure in conjugation with list decoding, Proceedings of 23rd International Symposium on Mathematical Theory of Networks and Systems, Hong Kong University of Science and Technology, Hong Kong, (2018), 309–314. Google Scholar
[26]	G. Landais and J.-P. Tillich, An efficient attack of a McEliece cryptosystem variant based on convolutional codes, International Workshop on Post-Quantum Cryptography, Springer, (2013), 102–117. Google Scholar
[27]	P. J. Lee and E. F. Brickell, An observation on the security of McEliece's public-key cryptosystem, Advances in Cryptology—EUROCRYPT '88 (Davos, 1988), Lecture Notes in Comput. Sci., Springer, Berlin, 330 (1988), 275-280. doi: 10.1007/3-540-45961-8_25. Google Scholar
[28]	J. S. Leon, A probabilistic algorithm for computing minimum weights of large error-correcting codes. Coding techniques and coding theory, IEEE Transactions on Information Theory, 34 (1988), 1354-1359. doi: 10.1109/18.21270. Google Scholar
[29]	C. Löndahl and T. Johansson, A new version of McEliece PKC based on convolutional codes, International Conference on Information and Communications Security, Springer, (2012), 461–470. Google Scholar
[30]	A. May and I. Ozerov, On computing nearest neighbors with applications to decoding of binary linear codes, Advances in Cryptology—EUROCRYPT 2015. Part Ⅰ, Lecture Notes in Comput. Sci., Springer, Heidelberg, 9056 (2015), 203-228. doi: 10.1007/978-3-662-46800-5_9. Google Scholar
[31]	R. J. McEliece, A Public-Key Cryptosystem Based on Algebraic Coding Theory, Technical report, DSN Progress report, Jet Propulsion Laboratory, Pasadena, 1978. Google Scholar
[32]	C. A. Melchor, N. Aragon, M. Bardet, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville, P. Gaborit, A. Hauteville, A. Otmani, O. Ruatta, J.-P. Tillich and G. Zémor, ROLLO-Rank-Ouroboros, LAKE & LOCKER, 2018. Google Scholar
[33]	L. Minder and A. Shokrollahi, Cryptanalysis of the Sidelnikov cryptosystem, Advances in Cryptology—EUROCRYPT 2007, Lecture Notes in Comput. Sci., Springer, Berlin, 4515 (2007), 347-360. doi: 10.1007/978-3-540-72540-4_20. Google Scholar
[34]	R. Misoczki, J.-P. Tillich, N. Sendrier and P. S. L. M. Barreto, MDPC-McEliece: New McEliece variants from moderate density parity-check codes, 2013 IEEE International Symposium on Information Theory, (2013), 2069–2073. doi: 10.1109/ISIT.2013.6620590. Google Scholar
[35]	R. Niebuhr, E. Persichetti, P.-L. Cayrel, S. Bulygin and J. Buchmann, On lower bounds for information set decoding over $\mathbb{F}_q$ and on the effect of partial knowledge, Int. J. Inf. Coding Theory, 4 (2017), 47-78. doi: 10.1504/IJICOT.2017.081458. Google Scholar
[36]	H. Niederreiter, Knapsack-type cryptosystems and algebraic coding theory, Problems Control Inform. Theory/Problemy Upravlen. Teor. Inform., 15 (1986), 159-166. Google Scholar
[37]	A. Otmani, J.-P. Tillich and L. Dallot, Cryptanalysis of two McEliece cryptosystems based on quasi-cyclic codes, Mathematics in Computer Science, 3 (2010), 129-140. doi: 10.1007/s11786-009-0015-8. Google Scholar
[38]	C. Peters, Information-set decoding for linear codes over $\mathbb{F}_q$, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 6061 (2010), 81–94, https://bitbucket.org/cbcrypto/isdfq/src/master/. doi: 10.1007/978-3-642-12929-2_7. Google Scholar
[39]	E. Prange, The use of information sets in decoding cyclic codes, IRE Transactions on Information Theory, 8 (1962), S5–S9. doi: 10.1109/tit.1962.1057777. Google Scholar
[40]	P. W. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, 35th Annual Symposium on Foundations of Computer Science (Santa Fe, NM, 1994), IEEE Comput. Soc. Press, Los Alamitos, CA, (1994), 124–134. doi: 10.1109/SFCS.1994.365700. Google Scholar
[41]	V. M. Sidelnikov, A public key cryptosystem based on Reed-Muller binary codes, Discrete Math. Appl., 4 (1994), 191-207. doi: 10.1515/dma.1994.4.3.191. Google Scholar
[42]	V. M. Sidelnikov and S. O. Shestakov, On an encoding system constructed on the basis of generalized Reed-Solomon codes, Diskret. Mat., 4 (1992), 57-63. doi: 10.1515/dma.1992.2.4.439. Google Scholar
[43]	V. M. Sidelnikov and S. O. Shestakov, On insecurity of cryptosystems based on generalized Reed-Solomon codes, Discrete Mathematics and Applications, 2 (1992), 439-444. Google Scholar
[44]	J. Stern, A method for finding codewords of small weight, Coding Theory and Applications, Lecture Notes in Comput. Sci., Springer, New Yorkpages, 388 (1989), 106-113. doi: 10.1007/BFb0019850. Google Scholar
[45]	A. Vardy and Y. Be'ery, Bit-level soft-decision decoding of Reed-Solomon codes, IEEE Transactions on Communications, 39 (1991), 440-444. Google Scholar
[46]	C. Wieschebrink, Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 6061 (2010), 61-72. doi: 10.1007/978-3-642-12929-2_5. Google Scholar
[47]	Y. Q. Wu, On expanded cyclic and Reed-Solomon codes, IEEE Transactions on Information Theory, 57 (2011), 601-620. doi: 10.1109/TIT.2010.2095150. Google Scholar

Table 1. Comparing key sizes of the proposed cryptosystem with $ m = 3 $ and $ \lambda = 2 $ reaching a $ 256 $-bit security level against the modified ISD algorithm

Rate	$ q $	$ n $	$ k $	$ t $	Key Size (bits)
0.60	13	1382	829	277	6783627
0.65	13	1270	825	223	5952804
0.70	13	1207	844	182	5339456
0.75	13	1192	894	149	4929077
0.80	13	1230	984	123	4702652
0.82	13	1258	1031	114	4624198
0.85	13	1340	1139	101	4634545
0.87	13	1420	1235	93	4692805
0.90	13	1602	1441	81	4863276

Table Options

Download as excel

Rate	$ q $	$ n $	$ k $	$ t $	Key Size (bits)
0.60	13	1382	829	277	6783627
0.65	13	1270	825	223	5952804
0.70	13	1207	844	182	5339456
0.75	13	1192	894	149	4929077
0.80	13	1230	984	123	4702652
0.82	13	1258	1031	114	4624198
0.85	13	1340	1139	101	4634545
0.87	13	1420	1235	93	4692805
0.90	13	1602	1441	81	4863276

Table 2. Comparing key sizes of the proposed cryptosystem with $ m = 4 $ and $ \lambda = 2 $ reaching a $ 256 $-bit security level against the modified ISD algorithm

Rate	$ q $	$ n $	$ k $	$ t $	Key Size (bits)
0.65	7	2360	1534	413	13134108
0.70	7	1945	1361	292	10191102
0.75	7	1738	1303	218	8480009
0.80	7	1662	1329	167	7448878
0.85	7	1700	1445	128	6815134
0.87	7	1770	1539	116	6785893
0.89	7	1872	1666	103	6754721
0.91	7	2024	1841	92	6814326

Table Options

Download as excel

Rate	$ q $	$ n $	$ k $	$ t $	Key Size (bits)
0.65	7	2360	1534	413	13134108
0.70	7	1945	1361	292	10191102
0.75	7	1738	1303	218	8480009
0.80	7	1662	1329	167	7448878
0.85	7	1700	1445	128	6815134
0.87	7	1770	1539	116	6785893
0.89	7	1872	1666	103	6754721
0.91	7	2024	1841	92	6814326

Table 3. Comparing the key sizes of the proposed parameters against different cryptosystems

		$ q $	$ m $	$ n $	$ k $	Key Size (in bits)
Proposed system	Type Ⅰs	13	3	1258	1031	4624198
Proposed system	Type Ⅱ	7	4	1872	1666	6754721
classical McEliece		2	13	6960	5413	8373911
BBCRS based schemes	$ w=1.708 $ and $ z=1 $	1423	1	1422	786	5113520
	$ w=1.2 $ and $ z=10 $	1163	1	1162	928	2274160
	$ w=2 $ and $ z=0 $	1993	1	1992	1593	6966714

Table Options

Download as excel

		$ q $	$ m $	$ n $	$ k $	Key Size (in bits)
Proposed system	Type Ⅰs	13	3	1258	1031	4624198
Proposed system	Type Ⅱ	7	4	1872	1666	6754721
classical McEliece		2	13	6960	5413	8373911
BBCRS based schemes	$ w=1.708 $ and $ z=1 $	1423	1	1422	786	5113520
	$ w=1.2 $ and $ z=10 $	1163	1	1162	928	2274160
	$ w=2 $ and $ z=0 $	1993	1	1992	1593	6966714

[1]	Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2021, 15 (1) : 113-130. doi: 10.3934/amc.2020046
[2]	Xiangrui Meng, Jian Gao. Complete weight enumerator of torsion codes. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020124
[3]	Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020118
[4]	Vito Napolitano, Ferdinando Zullo. Codes with few weights arising from linear sets. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020129
[5]	Dandan Wang, Xiwang Cao, Gaojun Luo. A class of linear codes and their complete weight enumerators. Advances in Mathematics of Communications, 2021, 15 (1) : 73-97. doi: 10.3934/amc.2020044
[6]	San Ling, Buket Özkaya. New bounds on the minimum distance of cyclic codes. Advances in Mathematics of Communications, 2021, 15 (1) : 1-8. doi: 10.3934/amc.2020038
[7]	Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045
[8]	Nicola Pace, Angelo Sonnino. On the existence of PD-sets: Algorithms arising from automorphism groups of codes. Advances in Mathematics of Communications, 2021, 15 (2) : 267-277. doi: 10.3934/amc.2020065
[9]	Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055
[10]	Sabira El Khalfaoui, Gábor P. Nagy. On the dimension of the subfield subcodes of 1-point Hermitian codes. Advances in Mathematics of Communications, 2021, 15 (2) : 219-226. doi: 10.3934/amc.2020054
[11]	Shanding Xu, Longjiang Qu, Xiwang Cao. Three classes of partitioned difference families and their optimal constant composition codes. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020120
[12]	Fengwei Li, Qin Yue, Xiaoming Sun. The values of two classes of Gaussian periods in index 2 case and weight distributions of linear codes. Advances in Mathematics of Communications, 2021, 15 (1) : 131-153. doi: 10.3934/amc.2020049
[13]	Hongming Ru, Chunming Tang, Yanfeng Qi, Yuxiao Deng. A construction of $ p $-ary linear codes with two or three weights. Advances in Mathematics of Communications, 2021, 15 (1) : 9-22. doi: 10.3934/amc.2020039
[14]	Tingting Wu, Li Liu, Lanqiang Li, Shixin Zhu. Repeated-root constacyclic codes of length $ 6lp^s $. Advances in Mathematics of Communications, 2021, 15 (1) : 167-189. doi: 10.3934/amc.2020051
[15]	Saadoun Mahmoudi, Karim Samei. Codes over $ \frak m $-adic completion rings. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020122
[16]	Hongwei Liu, Jingge Liu. On $ \sigma $-self-orthogonal constacyclic codes over $ \mathbb F_{p^m}+u\mathbb F_{p^m} $. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020127
[17]	Ivan Bailera, Joaquim Borges, Josep Rifà. On Hadamard full propelinear codes with associated group $ C_{2t}\times C_2 $. Advances in Mathematics of Communications, 2021, 15 (1) : 35-54. doi: 10.3934/amc.2020041
[18]	Yuan Cao, Yonglin Cao, Hai Q. Dinh, Ramakrishna Bandi, Fang-Wei Fu. An explicit representation and enumeration for negacyclic codes of length $ 2^kn $ over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021, 15 (2) : 291-309. doi: 10.3934/amc.2020067
[19]	Hai Q. Dinh, Bac T. Nguyen, Paravee Maneejuk. Constacyclic codes of length $ 8p^s $ over $ \mathbb F_{p^m} + u\mathbb F_{p^m} $. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020123
[20]	Shuyang Dai, Fengru Wang, Jerry Zhijian Yang, Cheng Yuan. A comparative study of atomistic-based stress evaluation. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020322

2019 Impact Factor: 0.734

Tools

Metrics

Tools

Article outline

Figures and Tables

2019 Impact Factor: 0.734

Tools

Figures and Tables

2019 Impact Factor: 0.734

American Institute of Mathematical Sciences

Encryption scheme based on expanded Reed-Solomon codes

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

Encryption scheme based on expanded Reed-Solomon codes

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors