Abstract
We propose a new decoding algorithm for random binary linear codes. The so-called information set decoding algorithm of Prange (1962) achieves worst-case complexity \(2^{0.121n}\). In the late 80s, Stern proposed a sort-and-match version for Prange’s algorithm, on which all variants of the currently best known decoding algorithms are build. The fastest algorithm of Becker, Joux, May and Meurer (2012) achieves running time \(2^{0.102n}\) in the full distance decoding setting and \(2^{0.0494n}\) with half (bounded) distance decoding.
In this work we point out that the sort-and-match routine in Stern’s algorithm is carried out in a non-optimal way, since the matching is done in a two step manner to realize an approximate matching up to a small number of error coordinates. Our observation is that such an approximate matching can be done by a variant of the so-called High Dimensional Nearest Neighbor Problem. Namely, out of two lists with entries from \({\mathbb F}_2^m\) we have to find a pair with closest Hamming distance. We develop a new algorithm for this problem with sub-quadratic complexity which might be of independent interest in other contexts.
Using our algorithm for full distance decoding improves Stern’s complexity from \(2^{0.117n}\) to \(2^{0.114n}\). Since the techniques of Becker et al apply for our algorithm as well, we eventually obtain the fastest decoding algorithm for binary linear codes with complexity \(2^{0.097n}\). In the half distance decoding scenario, we obtain a complexity of \(2^{0.0473n}\).
A. May—Supported by DFG as part of GRK 1817 Ubicrypt and SPP 1736 Big Data.
I. Ozerov—Supported by DFG as part of SPP 1307 Algorithm Engineering.
Chapter PDF
Similar content being viewed by others
References
Agarwal, P.K., Edelsbrunner, H., Schwarzkopf, O.: Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs. Discrete & Computational Geometry 6, 407–422 (1991)
Alekhnovich, M.: More on Average Case vs Approximation Complexity. In: 44th Symposium on Foundations of Computer Science (FOCS), pp. 298–307 (2003)
Becker, A., Coron, J.-S., Joux, A.: Improved Generic Algorithms for Hard Knapsacks. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 364–385. Springer, Heidelberg (2011)
Becker, A., Joux, A., May, A., Meurer, A.: Decoding random binary linear codes in \(2^{n/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)
Brakerski, Z., Vaikuntanathan, V.: Efficient Fully Homomorphic Encryption from (Standard) LWE. In: FOCS, pp. 97–106 (2011)
Dubiner, M., Bucketing coding and information theory for the statistical high-dimensional nearest-neighbor problem. IEEE Transactions on Information Theory 56(8), 4166–4179 (2010)
Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC, pp. 197–206 (2008)
Har-Peled, S., Indyk, P.: Rajeev Motwani Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality. Theory of Computing 8(1), 321–350 (2012)
Hopper, N.J., Blum, M.: Secure Human Identification Protocols. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 52–66. Springer, Heidelberg (2001)
Horowitz, E., Sahni, S.: Computing partitions with applications to the knapsack problem. J. ACM 21(2), 277–292 (1974)
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)
Kiltz, E., Pietrzak, K., Cash, D., Jain, A., Venturi, D.: Efficient Authentication from Hard Learning Problems. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 7–26. Springer, Heidelberg (2011)
Lee, P.J., Brickell, E.F.: An Observation on the Security of McEliece’s Public-Key Cryptosystem. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 275–280. Springer, Heidelberg (1988)
May, A., Meurer, A., Thomae, E.: Decoding Random Linear Codes in \(\tilde{\mathcal{O}}(2^{0.054n})\). In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 107–124. Springer, Heidelberg (2011)
McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. Jet Propulsion Laboratory DSN Progress Report 42–44, 114–116 (1978)
Peikert, C.: Brent Waters Lossy trapdoor functions and their applications. In: STOC, pp. 187–196 (2008)
Peters, C.: Information-Set Decoding for Linear Codes over \(\mathbb{F}_q\). In: Sendrier, N. (ed.) PQCrypto 2010. LNCS, vol. 6061, pp. 81–94. Springer, Heidelberg (2010)
Prange, E.: The Use of Information Sets in Decoding Cyclic Codes. IRE Transaction on Information Theory 8(5), 5–9 (1962)
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC, pp. 84–93 (2005)
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6) (2009)
Stern, J.: A method for finding codewords of small weight. In: Proceedings of the 3rd International Colloquium on Coding Theory and Applications, London, UK, pp. 106–113. Springer (1989)
Sudan, M.: Algorithmic Introduction to Coding Theory. Lecture Notes (available online) (2001)
Andoni, A., Indyk, P., Nguyen, H.L., Razenshteyn, I.: Beyond Locality-Sensitive Hashing. In: SODA, pp. 1018–1028 (2014)
Valiant, G.: Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas. In: FOCS, pp. 11–20 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 International Association for Cryptologic Research
About this paper
Cite this paper
May, A., Ozerov, I. (2015). On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes. In: Oswald, E., Fischlin, M. (eds) Advances in Cryptology -- EUROCRYPT 2015. EUROCRYPT 2015. Lecture Notes in Computer Science(), vol 9056. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46800-5_9
Download citation
DOI: https://doi.org/10.1007/978-3-662-46800-5_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46799-2
Online ISBN: 978-3-662-46800-5
eBook Packages: Computer ScienceComputer Science (R0)