doi: 10.3934/amc.2021062
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Niederreiter cryptosystems using quasi-cyclic codes that resist quantum Fourier sampling

1. 

Centre for quantum technologies and National University of Singapore, Singapore

2. 

IISER Pune, Pune, India

*Corresponding author: Ayan Mahalanobis

Received  September 2020 Revised  October 2021 Early access December 2021

McEliece and Niederreiter cryptosystems are robust and versatile cryptosystems. These cryptosystems work with many linear error-correcting codes. They are popular these days because they can be quantum-secure. In this paper, we study the Niederreiter cryptosystem using non-binary quasi-cyclic codes. We prove, if these quasi-cyclic codes satisfy certain conditions, the corresponding Niederreiter cryptosystem is resistant to the hidden subgroup problem using weak quantum Fourier sampling. Though our work uses the weak Fourier sampling, we argue that its conclusions should remain valid for the strong Fourier sampling as well.

Citation: Upendra Kapshikar, Ayan Mahalanobis. Niederreiter cryptosystems using quasi-cyclic codes that resist quantum Fourier sampling. Advances in Mathematics of Communications, doi: 10.3934/amc.2021062
References:
[1]

J. L. Alperin and R. B. Bell, Groups and Representations, Springer, 1995. doi: 10.1007/978-1-4612-0799-3.

[2]

D. Apon, R. Perlner, A. Robinson and P. Santini, Cryptanalysis of LEDAcrypt, Annual International Cryptology Conference, Springer, 12172 (2020), 389–418. doi: 10.1007/978-3-030-56877-1_14.

[3]

N. Aragon, P. Barreto, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville, P. Gaborit, S. Gueron, T. Guneysu, C. A. Melchor, et al., BIKE: Bit flipping key encapsulation.

[4]

M. Baldi, QC-LDPC Code-Based Cryptography, Springer, 2014. doi: 10.1007/978-3-319-02556-8.

[5]

M. BaldiM. BianchiF. ChiaralunceJ. Rosenthal and D. Schipani, Enhanced public key security for the McEliece cryptosystem, J. Cryptology, 29 (2016), 1-27.  doi: 10.1007/s00145-014-9187-8.

[6]

M. BaldiM. Bodrato and F. Chiaraluce, A new analysis of the McEliece cryptosystem based on QC-LDPC codes, Security and Cryptography for Networks, 5229 (2008), 246-262.  doi: 10.1007/978-3-540-85855-3_17.

[7]

M. Baldi, G. Cancellieri, F. Chiaraluce, E. Persichetti and P. Santini, Using non-binary LDPC and MDPC codes in the McEliece cryptosystem, AEIT International Annual Conference (AEIT), (2019), 1–6.

[8]

M. Baldi and F. Chiaraluce, Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes, 2007 IEEE International Symposium on Information Theory, IEEE, (2007), 2591–2595.

[9]

M. Baldi, et al., LEDAcrypt: Low-density parity-check code-based cryptographic systems, NIST Round 2 Submission for Post-Quantum Cryptography, 2019.

[10]

T. P. BergerP.-L. CayrelP. Gaborit and A. Otmani, Reducing key length of the McEliece cryptosystem, Progress in cryptology–AFRICACRYPT 2009, 5580 (2009), 77-97.  doi: 10.1007/978-3-642-02384-2_6.

[11]

P. J. Davis, Circulant Matrices, New York-Chichester-Brisbane, 1979.

[12]

D. Declercq and M. Fossorier, Decoding algortihms for non-binary LDPC codes over $GF(q)$, IEEE Transactions on Communications, 55 (2007), 633-643. 

[13]

H. DinhC. Moore and A. Russell, McEliece and Niederreiter cryptosystems that resist quantum fourier sampling attacks, Advances in Cryptology – CRYPTO 2011, 6841 (2011), 761-779.  doi: 10.1007/978-3-642-22792-9_43.

[14]

J. D. Dixon and B. Mortimer, Permutation Groups, Graduate Texts in Mathematics, Springer, New York, 1996. doi: 10.1007/978-1-4612-0731-3.

[15]

P. Gaborit, Shorter keys for code based cryptography, Proceedings of the International Workshop on Coding and Cryptography, 2005, (2005), 81–91.

[16]

M. Grigni, L. Schulman, M. Vazirani and U. Vazirani, Quantum mechanical algorithms for the nonabelian hidden subgroup problem, Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, ACM, (2001), 68–74. doi: 10.1145/380752.380769.

[17]

T. A. Gulliver, Construction of Quasi-cyclic Codes, PhD thesis, University of Victoria, 1989.

[18]

S. HallgrenA. Russell and A. Ta-Shma, The hidden subgroup problem and quantum computation using group representation, SIAM J. Comput., 32 (2003), 916-934.  doi: 10.1137/S009753970139450X.

[19]

S. Hallgren, A. Russell and A. Ta-Shma, Normal subgroup reconstruction and quantum computation using group representations, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC '00, ACM, New York, NY, USA, (2000), 627–635. doi: 10.1145/335305.335392.

[20]

G. IvanyosF. Magniez and M. Santha, Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem, Internat. J. Found. Comput. Sci., 14 (2003), 723-739.  doi: 10.1142/S0129054103001996.

[21]

U. Kapshikar and A. Mahalanobis, A quantum-secure {Niederreiter Cryptosystem} using quasi-cyclic codes, Proceedings of the 15th International Joint Conference on e-Business and Telecommunications, SECRYPT, (2018), 506–513. doi: 10.5220/0006843005060513.

[22]

J. KempeL. Pyber and A. Shalev, Permutation groups, minimal degrees and quantum computing, Groups Geom. Dyn., 1 (2007), 553-584.  doi: 10.4171/GGD/24.

[23]

J. Kempe and A. Shalev, The hidden subgroup problem and permutation group theory, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, (2005), 1118–1125.

[24]

K. Lally and P. Fitzpatrick, Algebraic structure of quasicyclic codes, Discrete Appl. Math., 111 (2001), 157-175.  doi: 10.1016/S0166-218X(00)00350-4.

[25]

R. J. McElice, A Public Key Cryptosystem Based on Algebraic Coding Theory, Technical report, Communications system research centre, NASA, 1978.

[26]

C. Monico, J. Rosenthal and A. Shokrollahi, Using low density parity check codes in the McEliece cryptosystem, 2000 IEEE International Symposium on Information Theory, IEEE, (2000), 215. doi: 10.1109/ISIT.2000.866513.

[27]

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

[28]

A. OtmaniJ.-P. Tillich and L. Dallot, Cryptanalysis of two McEliece cryptosystems based on quasi-cyclic codes, Math. Comput. Sci., 3 (2010), 129-140.  doi: 10.1007/s11786-009-0015-8.

[29]

M. Roetteler and T. Beth, Polynomial-time solution to the hidden subgroup problem for a class of non-abelian groups, arXiv preprint, quant-ph/9812070.

[30]

P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM review, 41 (1999), 303-332.  doi: 10.1137/S0036144598347011.

[31]

J. Watrous, Succinct quantum proofs for properties of finite groups, Proceedings 41st Annual Symposium on Foundations of Computer Science, (2000), 537–546, http://arXiv.org/abs/cs.CC/0009002. doi: 10.1109/SFCS.2000.892141.

[32]

A. Yamada, et al., QC-MDPC KEM: A key encapsulation mechanishm based on the QC-MDPC McEliece encryption scheme, NIST Round 1 Submission for Post-Quantum Cryptography, 2017.

show all references

References:
[1]

J. L. Alperin and R. B. Bell, Groups and Representations, Springer, 1995. doi: 10.1007/978-1-4612-0799-3.

[2]

D. Apon, R. Perlner, A. Robinson and P. Santini, Cryptanalysis of LEDAcrypt, Annual International Cryptology Conference, Springer, 12172 (2020), 389–418. doi: 10.1007/978-3-030-56877-1_14.

[3]

N. Aragon, P. Barreto, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville, P. Gaborit, S. Gueron, T. Guneysu, C. A. Melchor, et al., BIKE: Bit flipping key encapsulation.

[4]

M. Baldi, QC-LDPC Code-Based Cryptography, Springer, 2014. doi: 10.1007/978-3-319-02556-8.

[5]

M. BaldiM. BianchiF. ChiaralunceJ. Rosenthal and D. Schipani, Enhanced public key security for the McEliece cryptosystem, J. Cryptology, 29 (2016), 1-27.  doi: 10.1007/s00145-014-9187-8.

[6]

M. BaldiM. Bodrato and F. Chiaraluce, A new analysis of the McEliece cryptosystem based on QC-LDPC codes, Security and Cryptography for Networks, 5229 (2008), 246-262.  doi: 10.1007/978-3-540-85855-3_17.

[7]

M. Baldi, G. Cancellieri, F. Chiaraluce, E. Persichetti and P. Santini, Using non-binary LDPC and MDPC codes in the McEliece cryptosystem, AEIT International Annual Conference (AEIT), (2019), 1–6.

[8]

M. Baldi and F. Chiaraluce, Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes, 2007 IEEE International Symposium on Information Theory, IEEE, (2007), 2591–2595.

[9]

M. Baldi, et al., LEDAcrypt: Low-density parity-check code-based cryptographic systems, NIST Round 2 Submission for Post-Quantum Cryptography, 2019.

[10]

T. P. BergerP.-L. CayrelP. Gaborit and A. Otmani, Reducing key length of the McEliece cryptosystem, Progress in cryptology–AFRICACRYPT 2009, 5580 (2009), 77-97.  doi: 10.1007/978-3-642-02384-2_6.

[11]

P. J. Davis, Circulant Matrices, New York-Chichester-Brisbane, 1979.

[12]

D. Declercq and M. Fossorier, Decoding algortihms for non-binary LDPC codes over $GF(q)$, IEEE Transactions on Communications, 55 (2007), 633-643. 

[13]

H. DinhC. Moore and A. Russell, McEliece and Niederreiter cryptosystems that resist quantum fourier sampling attacks, Advances in Cryptology – CRYPTO 2011, 6841 (2011), 761-779.  doi: 10.1007/978-3-642-22792-9_43.

[14]

J. D. Dixon and B. Mortimer, Permutation Groups, Graduate Texts in Mathematics, Springer, New York, 1996. doi: 10.1007/978-1-4612-0731-3.

[15]

P. Gaborit, Shorter keys for code based cryptography, Proceedings of the International Workshop on Coding and Cryptography, 2005, (2005), 81–91.

[16]

M. Grigni, L. Schulman, M. Vazirani and U. Vazirani, Quantum mechanical algorithms for the nonabelian hidden subgroup problem, Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, ACM, (2001), 68–74. doi: 10.1145/380752.380769.

[17]

T. A. Gulliver, Construction of Quasi-cyclic Codes, PhD thesis, University of Victoria, 1989.

[18]

S. HallgrenA. Russell and A. Ta-Shma, The hidden subgroup problem and quantum computation using group representation, SIAM J. Comput., 32 (2003), 916-934.  doi: 10.1137/S009753970139450X.

[19]

S. Hallgren, A. Russell and A. Ta-Shma, Normal subgroup reconstruction and quantum computation using group representations, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC '00, ACM, New York, NY, USA, (2000), 627–635. doi: 10.1145/335305.335392.

[20]

G. IvanyosF. Magniez and M. Santha, Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem, Internat. J. Found. Comput. Sci., 14 (2003), 723-739.  doi: 10.1142/S0129054103001996.

[21]

U. Kapshikar and A. Mahalanobis, A quantum-secure {Niederreiter Cryptosystem} using quasi-cyclic codes, Proceedings of the 15th International Joint Conference on e-Business and Telecommunications, SECRYPT, (2018), 506–513. doi: 10.5220/0006843005060513.

[22]

J. KempeL. Pyber and A. Shalev, Permutation groups, minimal degrees and quantum computing, Groups Geom. Dyn., 1 (2007), 553-584.  doi: 10.4171/GGD/24.

[23]

J. Kempe and A. Shalev, The hidden subgroup problem and permutation group theory, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, (2005), 1118–1125.

[24]

K. Lally and P. Fitzpatrick, Algebraic structure of quasicyclic codes, Discrete Appl. Math., 111 (2001), 157-175.  doi: 10.1016/S0166-218X(00)00350-4.

[25]

R. J. McElice, A Public Key Cryptosystem Based on Algebraic Coding Theory, Technical report, Communications system research centre, NASA, 1978.

[26]

C. Monico, J. Rosenthal and A. Shokrollahi, Using low density parity check codes in the McEliece cryptosystem, 2000 IEEE International Symposium on Information Theory, IEEE, (2000), 215. doi: 10.1109/ISIT.2000.866513.

[27]

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

[28]

A. OtmaniJ.-P. Tillich and L. Dallot, Cryptanalysis of two McEliece cryptosystems based on quasi-cyclic codes, Math. Comput. Sci., 3 (2010), 129-140.  doi: 10.1007/s11786-009-0015-8.

[29]

M. Roetteler and T. Beth, Polynomial-time solution to the hidden subgroup problem for a class of non-abelian groups, arXiv preprint, quant-ph/9812070.

[30]

P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM review, 41 (1999), 303-332.  doi: 10.1137/S0036144598347011.

[31]

J. Watrous, Succinct quantum proofs for properties of finite groups, Proceedings 41st Annual Symposium on Foundations of Computer Science, (2000), 537–546, http://arXiv.org/abs/cs.CC/0009002. doi: 10.1109/SFCS.2000.892141.

[32]

A. Yamada, et al., QC-MDPC KEM: A key encapsulation mechanishm based on the QC-MDPC McEliece encryption scheme, NIST Round 1 Submission for Post-Quantum Cryptography, 2017.

[1]

Jintai Ding, Sihem Mesnager, Lih-Chung Wang. Letters for post-quantum cryptography standard evaluation. Advances in Mathematics of Communications, 2020, 14 (1) : i-i. doi: 10.3934/amc.2020012

[2]

Enhui Lim, Frédérique Oggier. On the generalised rank weights of quasi-cyclic codes. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022010

[3]

Fernando Hernando, Tom Høholdt, Diego Ruano. List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes. Advances in Mathematics of Communications, 2012, 6 (3) : 259-272. doi: 10.3934/amc.2012.6.259

[4]

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

[5]

Martianus Frederic Ezerman, San Ling, Patrick Solé, Olfa Yemen. From skew-cyclic codes to asymmetric quantum codes. Advances in Mathematics of Communications, 2011, 5 (1) : 41-57. doi: 10.3934/amc.2011.5.41

[6]

Marco Castrillón López, Pedro Luis García Pérez. The problem of Lagrange on principal bundles under a subgroup of symmetries. Journal of Geometric Mechanics, 2019, 11 (4) : 539-552. doi: 10.3934/jgm.2019026

[7]

Santanu Sarkar. Analysis of Hidden Number Problem with Hidden Multiplier. Advances in Mathematics of Communications, 2017, 11 (4) : 805-811. doi: 10.3934/amc.2017059

[8]

Lidong Chen, Dustin Moody. New mission and opportunity for mathematics researchers: Cryptography in the quantum era. Advances in Mathematics of Communications, 2020, 14 (1) : 161-169. doi: 10.3934/amc.2020013

[9]

Cem Güneri, Ferruh Özbudak, Funda ÖzdemIr. On complementary dual additive cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 353-357. doi: 10.3934/amc.2017028

[10]

Nabil Bennenni, Kenza Guenda, Sihem Mesnager. DNA cyclic codes over rings. Advances in Mathematics of Communications, 2017, 11 (1) : 83-98. doi: 10.3934/amc.2017004

[11]

Heide Gluesing-Luerssen, Katherine Morrison, Carolyn Troha. Cyclic orbit codes and stabilizer subfields. Advances in Mathematics of Communications, 2015, 9 (2) : 177-197. doi: 10.3934/amc.2015.9.177

[12]

Mustapha Ait Rami, John Moore. Partial stabilizability and hidden convexity of indefinite LQ problem. Numerical Algebra, Control and Optimization, 2016, 6 (3) : 221-239. doi: 10.3934/naco.2016009

[13]

Ram Krishna Verma, Om Prakash, Ashutosh Singh, Habibul Islam. New quantum codes from skew constacyclic codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021028

[14]

Ramprasad Sarkar, Mriganka Mandal, Sourav Mukhopadhyay. Quantum-safe identity-based broadcast encryption with provable security from multivariate cryptography. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022026

[15]

Heide Gluesing-Luerssen, Fai-Lung Tsang. A matrix ring description for cyclic convolutional codes. Advances in Mathematics of Communications, 2008, 2 (1) : 55-81. doi: 10.3934/amc.2008.2.55

[16]

Rafael Arce-Nazario, Francis N. Castro, Jose Ortiz-Ubarri. On the covering radius of some binary cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 329-338. doi: 10.3934/amc.2017025

[17]

Long Yu, Hongwei Liu. A class of $p$-ary cyclic codes and their weight enumerators. Advances in Mathematics of Communications, 2016, 10 (2) : 437-457. doi: 10.3934/amc.2016017

[18]

Umberto Martínez-Peñas. Rank equivalent and rank degenerate skew cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 267-282. doi: 10.3934/amc.2017018

[19]

Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83

[20]

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

2021 Impact Factor: 1.015

Article outline

[Back to Top]