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

Upendra Kapshikar; Ayan Mahalanobis

doi:10.3934/amc.2021062

Article Contents

2023, Volume 17, Issue 6: 1476-1492. Doi: 10.3934/amc.2021062

This issue Previous Article Differential spectra of a class of power permutations with Niho exponents Next Article Aperiodic/periodic complementary sequence pairs over quaternions

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

Upendra Kapshikar^1, and
Ayan Mahalanobis^2, ,

1.
Centre for quantum technologies and National University of Singapore, Singapore
2.
IISER Pune, Pune, India

^*Corresponding author: Ayan Mahalanobis
^*Corresponding author: Ayan Mahalanobis

Received: September 2020

Revised: October 2021

Early access: December 15, 2021

Published online: December 15, 2021

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 94A60, 81P94; Secondary: 94B05.

Citation:

Full Text(HTML)

Related Papers

Cited by

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. Baldi, M. Bianchi, F. Chiaralunce, J. 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. Baldi, M. 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. Berger, P.-L. Cayrel, P. 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. Dinh, C. 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. Hallgren, A. 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. Ivanyos, F. 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. Kempe, L. 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. Otmani, J.-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.