Abstract
The security of code-based cryptosystems such as the McEliece cryptosystem relies primarily on the difficulty of decoding random linear codes. The best decoding algorithms are all improvements of an old algorithm due to Prange: they are known under the name of information set decoding techniques. It is also important to assess the security of such cryptosystems against a quantum computer. This research thread started in [23] and the best algorithm to date has been Bernstein’s quantising [5] of the simplest information set decoding algorithm, namely Prange’s algorithm. It consists in applying Grover’s quantum search to obtain a quadratic speed-up of Prange’s algorithm. In this paper, we quantise other information set decoding algorithms by using quantum walk techniques which were devised for the subset-sum problem in [6]. This results in improving the worst-case complexity of \(2^{0.06035n}\) of Bernstein’s algorithm to \(2^{0.05869n}\) with the best algorithm presented here (where n is the codelength).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
An information set of a linear code C of dimension k is a set \({\mathscr {I}}\) of k positions such that when given \(\{c_i:i \in {\mathscr {I}}\}\) the codeword c of C is specified entirely.
- 2.
In the case of Dumer’s algorithm, for instance, even if the restriction of e to \({\fancyscript{S}}\) is of weight p, Dumer’s algorithm may fail to find it since it does not split evenly on both sides of the bipartition of \({\fancyscript{S}}\).
References
Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37, 210–239 (2007)
Barg, A.: Complexity issues in coding theory. In: Electronic Colloquium on Computational Complexity, October 1997
Becker, A.: The representation technique, applications to hard problems in cryptography. Ph.D. thesis, Université Versailles Saint-Quentin en Yvelines, October 2012
Becker, A., Joux, A., May, A., Meurer, A.: Decoding random binary linear codes in 2n/20: how \(1+1=0\) improves information set decoding. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 520–536. Springer, Heidelberg (2012). doi:10.1007/978-3-642-29011-4_31
Bernstein, D.J.: Grover vs. McEliece. In: Sendrier, N. (ed.) PQCrypto 2010. LNCS, vol. 6061, pp. 73–80. Springer, Heidelberg (2010). doi:10.1007/978-3-642-12929-2_6
Bernstein, D.J., Jeffery, S., Lange, T., Meurer, A.: Quantum algorithms for the subset-sum problem. In: Gaborit, P. (ed.) PQCrypto 2013. LNCS, vol. 7932, pp. 16–33. Springer, Heidelberg (2013). doi:10.1007/978-3-642-38616-9_2
Bernstein, D.J., Lange, T., Peters, C.: Smaller decoding exponents: ball-collision decoding. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 743–760. Springer, Heidelberg (2011). doi:10.1007/978-3-642-22792-9_42
Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortsch. Phys. 46, 493 (1998)
Canto Torres, R., Sendrier, N.: Analysis of information set decoding for a sub-linear error weight. In: Takagi, T. (ed.) PQCrypto 2016. LNCS, vol. 9606, pp. 144–161. Springer, Cham (2016). doi:10.1007/978-3-319-29360-8_10
Cvetković, D.M., Doob, M., Sachs, H.: Spectra of Graphs: Theory and Application. Academic Press, New York (1980)
Dumer, I.: On minimum distance decoding of linear codes. In: Proceedings of 5th Joint Soviet-Swedish International Workshop Information Theory, Moscow, pp. 50–52 (1991)
Finiasz, M., Sendrier, N.: Security bounds for the design of code-based cryptosystems. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 88–105. Springer, Heidelberg (2009). doi:10.1007/978-3-642-10366-7_6
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings 28th Annual ACM Symposium on the Theory of Computation, pp. 212–219. ACM Press, New York (1996)
Grover, L.K.: Quantum computers can search arbitrarily large databases by a single query. Phys. Rev. Lett. 79, 4709–4712 (1997)
Howgrave-Graham, N., Joux, A.: New generic algorithms for hard knapsacks. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 235–256. Springer, Heidelberg (2010). doi:10.1007/978-3-642-13190-5_12
Kachigar, G. Étude et conception d’algorithmes quantiques pour le décodage de codes linéaires. Master’s thesis, Université de Rennes 1, France, September 2016
Kachigar, G., Tillich, J.-P.: Quantum information set decoding algorithms. preprint, arXiv:1703.00263 [cs.CR], February 2017
Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC 2007, pp. 575–584 (2007)
May, A., Meurer, A., Thomae, E.: Decoding random linear codes in \(\tilde{\cal{O}}(2^{0.054n})\). In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 107–124. Springer, Heidelberg (2011). doi:10.1007/978-3-642-25385-0_6
May, A., Ozerov, I.: On computing nearest neighbors with applications to decoding of binary linear codes. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 203–228. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46800-5_9
McEliece, R.J.: A public-key system based on algebraic coding theory, pp. 114–116. Jet Propulsion Laboratory (1978). DSN Progress Report 44
Niederreiter, H.: Knapsack-type cryptosystems and algebraic coding theory. Probl. Control Inf. Theory 15(2), 159–166 (1986)
Overbeck, R., Sendrier, N.: Code-based cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.) Post-Quantum Cryptography, pp. 95–145. Springer, Heidelberg (2009)
Prange, E.: The use of information sets in decoding cyclic codes. IRE Trans. Inf. Theory 8(5), 5–9 (1962)
Santha, M.: Quantum walk based search algorithms. In: 5th TAMC, pp. 31–46. arXiv:0808.0059 (2008)
Schroeppel, R., Shamir, A.: A \(T=O(2^{n/2})\), \(S=O(2^{n/4})\) algorithm for certain NP-complete problems. SIAM J. Comput. 10(3), 456–464 (1981)
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)
Stern, J.: A method for finding codewords of small weight. In: Cohen, G., Wolfmann, J. (eds.) Coding Theory 1988. LNCS, vol. 388, pp. 106–113. Springer, Heidelberg (1989). doi:10.1007/BFb0019850
Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pp. 32–41 (2004)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Kachigar, G., Tillich, JP. (2017). Quantum Information Set Decoding Algorithms. In: Lange, T., Takagi, T. (eds) Post-Quantum Cryptography . PQCrypto 2017. Lecture Notes in Computer Science(), vol 10346. Springer, Cham. https://doi.org/10.1007/978-3-319-59879-6_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-59879-6_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-59878-9
Online ISBN: 978-3-319-59879-6
eBook Packages: Computer ScienceComputer Science (R0)