American Institute of Mathematical Sciences

Advanced
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  May 2021 Early access  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.

[2]

M. Albrecht, C. Cid, K. G. Paterson, C. J. Tjhai and M. Tomlinson, NTS-KEM, 2018.

[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.

[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. 

[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.

[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.

[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.

[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).

[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.

[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.

[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.

[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.

[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.

[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. 

[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.

[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.

[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.

[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.

[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.

[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.

[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. 

[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.

[23]

C. Interlando, K. Khathuria, N. Rohrer, J. Rosenthal and V. Weger, Generalization of the ball-collision algorithm, Preprint, (2018), arXiv: 1812.10955.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[31]

R. J. McEliece, A Public-Key Cryptosystem Based on Algebraic Coding Theory, Technical report, DSN Progress report, Jet Propulsion Laboratory, Pasadena, 1978.

[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.

[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.

[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.

[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.

[36]

H. Niederreiter, Knapsack-type cryptosystems and algebraic coding theory, Problems Control Inform. Theory/Problemy Upravlen. Teor. Inform., 15 (1986), 159-166. 

[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.

[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.

[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.

[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.

[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.

[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.

[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. 

[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.

[45]

A. Vardy and Y. Be'ery, Bit-level soft-decision decoding of Reed-Solomon codes, IEEE Transactions on Communications, 39 (1991), 440-444. 

[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.

[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.

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.

[2]

M. Albrecht, C. Cid, K. G. Paterson, C. J. Tjhai and M. Tomlinson, NTS-KEM, 2018.

[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.

[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. 

[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.

[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.

[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.

[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).

[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.

[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.

[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.

[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.

[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.

[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. 

[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.

[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.

[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.

[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.

[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.

[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.

[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. 

[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.

[23]

C. Interlando, K. Khathuria, N. Rohrer, J. Rosenthal and V. Weger, Generalization of the ball-collision algorithm, Preprint, (2018), arXiv: 1812.10955.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[31]

R. J. McEliece, A Public-Key Cryptosystem Based on Algebraic Coding Theory, Technical report, DSN Progress report, Jet Propulsion Laboratory, Pasadena, 1978.

[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.

[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.

[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.

[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.

[36]

H. Niederreiter, Knapsack-type cryptosystems and algebraic coding theory, Problems Control Inform. Theory/Problemy Upravlen. Teor. Inform., 15 (1986), 159-166. 

[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.

[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.

[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.

[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.

[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.

[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.

[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. 

[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.

[45]

A. Vardy and Y. Be'ery, Bit-level soft-decision decoding of Reed-Solomon codes, IEEE Transactions on Communications, 39 (1991), 440-444. 

[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.

[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.

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
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
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]

Yujuan Li, Guizhen Zhu. On the error distance of extended Reed-Solomon codes. Advances in Mathematics of Communications, 2016, 10 (2) : 413-427. doi: 10.3934/amc.2016015
[2]

Peter Beelen, David Glynn, Tom Høholdt, Krishna Kaipa. Counting generalized Reed-Solomon codes. Advances in Mathematics of Communications, 2017, 11 (4) : 777-790. doi: 10.3934/amc.2017057
[3]

Antonio Cafure, Guillermo Matera, Melina Privitelli. Singularities of symmetric hypersurfaces and Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (1) : 69-94. doi: 10.3934/amc.2012.6.69
[4]

Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005
[5]

José Moreira, Marcel Fernández, Miguel Soriano. On the relationship between the traceability properties of Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (4) : 467-478. doi: 10.3934/amc.2012.6.467
[6]

Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399
[7]

Martino Borello, Olivier Mila. Symmetries of weight enumerators and applications to Reed-Muller codes. Advances in Mathematics of Communications, 2019, 13 (2) : 313-328. doi: 10.3934/amc.2019021
[8]

Daniele Bartoli, Adnen Sboui, Leo Storme. Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes. Advances in Mathematics of Communications, 2016, 10 (2) : 355-365. doi: 10.3934/amc.2016010
[9]

Olav Geil, Stefano Martin. Relative generalized Hamming weights of q-ary Reed-Muller codes. Advances in Mathematics of Communications, 2017, 11 (3) : 503-531. doi: 10.3934/amc.2017041
[10]

Andreas Klein, Leo Storme. On the non-minimality of the largest weight codewords in the binary Reed-Muller codes. Advances in Mathematics of Communications, 2011, 5 (2) : 333-337. doi: 10.3934/amc.2011.5.333
[11]

Ettore Fornasini, Telma Pinho, Raquel Pinto, Paula Rocha. Composition codes. Advances in Mathematics of Communications, 2016, 10 (1) : 163-177. doi: 10.3934/amc.2016.10.163
[12]

Alexis Eduardo Almendras Valdebenito, Andrea Luigi Tironi. On the dual codes of skew constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (4) : 659-679. doi: 10.3934/amc.2018039
[13]

Michael Braun. On lattices, binary codes, and network codes. Advances in Mathematics of Communications, 2011, 5 (2) : 225-232. doi: 10.3934/amc.2011.5.225
[14]

Anna-Lena Horlemann-Trautmann, Kyle Marshall. New criteria for MRD and Gabidulin codes and some Rank-Metric code constructions. Advances in Mathematics of Communications, 2017, 11 (3) : 533-548. doi: 10.3934/amc.2017042
[15]

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
[16]

Terry Shue Chien Lau, Chik How Tan. Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020132
[17]

Grégory Berhuy. Algebraic space-time codes based on division algebras with a unitary involution. Advances in Mathematics of Communications, 2014, 8 (2) : 167-189. doi: 10.3934/amc.2014.8.167
[18]

Michel Lavrauw, Geertrui Van de Voorde. Locally repairable codes with high availability based on generalised quadrangles. Advances in Mathematics of Communications, 2022, 16 (1) : 73-81. doi: 10.3934/amc.2020099
[19]

Joaquim Borges, Josep Rifà, Victor Zinoviev. Completely regular codes by concatenating Hamming codes. Advances in Mathematics of Communications, 2018, 12 (2) : 337-349. doi: 10.3934/amc.2018021
[20]

Can Xiang, Jinquan Luo. Some subfield codes from MDS codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021023

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (622)
  • HTML views (966)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy