Abstract
In this paper we present quantum information set decoding (ISD) algorithms for binary linear codes. First, we refine the analysis of the quantum walk based algorithms proposed by Kachigar and Tillich (PQCrypto’17). This refinement allows us to improve the running time of quantum decoding in the leading order term: for an n-dimensional binary linear code the complexity of May-Meurer-Thomae ISD algorithm (Asiacrypt’11) drops down from \(2^{0.05904n + o(n)}\) to \(2^{0.05806n+o(n)}\). Similar improvement is achieved for our quantum version of Becker-Jeux-May-Meurer (Eurocrypt’12) decoding algorithm. Second, we translate May-Ozerov Near Neighbour technique (Eurocrypt’15) to an ‘update-and-query’ language more common in a similarity search literature. This re-interpretation allows us to combine Near Neighbour search with the quantum walk framework and use both techniques to improve a quantum version of Dumer’s ISD algorithm: the running time goes down from \(2^{0.059962n+o(n)}\) to \(2^{0.059450+o(n)}\).
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.
We omit sub-exponential in n factors throughout, because we are only interested in the constant \(\mathsf {c}\). Furthermore, our analysis is for an average case and we sometimes omit the word ‘expected’.
- 2.
The (dimensionless) distances we consider here, denoted further \(\gamma , \alpha , \beta \), are all \(\le 1/2\), since we can flip the bits of the query point and search for ‘close’ rather than ‘far apart’ vectors.
- 3.
By ‘error’ we mean missing a vector which is \(\gamma \)-close to \({\mathbf {q}}\).
- 4.
One could also run Grover inside each bucket during the Query phase, when the buckets are larger than 1. This, however, does not seem to bring an improvement.
References
Ambainis, A.: Quantum walk algorithm for element distinctness. In: FOCS, pp. 210–239 (2004)
Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs. Springer, Heidelberg (1989). https://doi.org/10.1007/978-3-642-74341-2
Becker, A., Ducas, L., Gama, N., Laarhoven, T.: New directions in nearest neighbor searching with applications to lattice sieving. In: SODA 2016, pp. 10–24 (2016)
Bernstein, D.J.: Grover vs. McEliece. In: Sendrier, N. (ed.) PQCrypto 2010. LNCS, vol. 6061, pp. 73–80. Springer, Heidelberg (2010). https://doi.org/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). https://doi.org/10.1007/978-3-642-38616-9_2
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). https://doi.org/10.1007/978-3-642-29011-4_31
Both, L., May, A.: Optimizing BJMM with nearest neighbors: full decoding in \({2^{2 n/21}}\) and McEliece security. In: The Tenth International Workshop on Coding and Cryptography (2017)
Childs, A.M., Eisenberg, J.M.: Quantum algorithms for subset finding. Quantum Inf. Comput. 5(7), 593–604 (2005)
Christiani, T.: A framework for similarity search with space-time tradeoffs using locality-sensitive filtering. In: SODA, pp. 31–46 (2017)
Dumer, I.: On minimum distance decoding of linear codes. In: Proceedings of the 5th Joint Soviet-Swedish International Workshop on Information Theory, pp. 50–52 (1991)
Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 604–613 (1998)
Kirshanova, E.: Improved quantum information set decoding (2018). http://perso.ens-lyon.fr/elena.kirshanova/Papers/quantumISD.pdf
Kachigar, G., Tillich, J.-P.: Quantum information set decoding algorithms. In: Lange, T., Takagi, T. (eds.) PQCrypto 2017. LNCS, vol. 10346, pp. 69–89. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59879-6_5
Laarhoven, T.: Tradeoffs for nearest neighbors on the sphere. CoRR, abs/1511.07527 (2015)
McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. In: Deep Space Network Progress Report, pp. 114–116 (1978)
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). https://doi.org/10.1007/978-3-642-25385-0_6
Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. SIAM J. Comput. 40(1), 142–164 (2011)
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). https://doi.org/10.1007/978-3-662-46800-5_9
Prange, E.: The use of information sets in decoding cyclic codes. IRE Trans. Inf. Theory 6, 5–9 (1962)
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, 456–464 (1981)
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). https://doi.org/10.1007/BFb0019850
Acknowledgements
The author thanks Alexander May for enlightening discussions and suggestions. This work is supported by ERC Starting Grant ERC-2013-StG-335086-LATTAC.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Kirshanova, E. (2018). Improved Quantum Information Set Decoding. In: Lange, T., Steinwandt, R. (eds) Post-Quantum Cryptography. PQCrypto 2018. Lecture Notes in Computer Science(), vol 10786. Springer, Cham. https://doi.org/10.1007/978-3-319-79063-3_24
Download citation
DOI: https://doi.org/10.1007/978-3-319-79063-3_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-79062-6
Online ISBN: 978-3-319-79063-3
eBook Packages: Computer ScienceComputer Science (R0)