Generalization of the ball-collision algorithm
DOI:
https://doi.org/10.13069/jacodesmath.729477Keywords:
Coding theory, ISD, Ball-collisionAbstract
In this paper we generalize the ball-collision algorithm by Bernstein, Lange, Peters from the binary field to a general finite field. We also provide a complexity analysis and compare the asymptotic complexity to other generalized information set decoding algorithms.
Received: 10 September 2019 | Accepted: 18 April 2020Downloads
References
A. Al Jabri, A statistical decoding algorithm for general linear block codes, in: Cryptography and Coding, Lecture Notes in Comput. Sci., vol. 2260, Springer, Berlin, Heidelberg (2001) 1–8.
A. Ashikhmin and A. Barg, Minimal vectors in linear codes, IEEE Trans. Inform. Theory 44(5) (1998) 2010–2017.
M. Baldi, M. Bianchi, F. Chiaraluce, J. Rosenthal, and D. Schipani, Enhanced public key security for the McEliece cryptosystem, J. Cryptology 29(1) (2016) 1–27.
G. Banegas, P. S. L. M. Barreto, B. O. Boidje, P.-L. Cayrel, G. N. Dione, K. Gaj, C. T. Gueye, R. Haeussler, J. B. Klamti, O. N'diaye, et al., DAGS: Key encapsulation using dyadic GS codes, J. Math. Cryptol. 12(4) (2018) 221–239.
A. Barg, E. Krouk, and H. C. A. van Tilborg, On the complexity of minimum distance decoding of long linear codes, IEEE Trans. Inform. Theory 45(5) (1999) 1392–1405.
A. Becker, A. Joux, A. May, and A. Meurer, Decoding random binary linear codes in $2^{n/20}$: How $1+1=0$ improves information set decoding, in: Advances in Cryptology – EUROCRYPT 2012, Lecture Notes in Comput. Sci., vol. 7237, Springer, Berlin, Heidelberg (2012) 520–536.
E. R. Berlekamp, R. J. McEliece, and H. C. A. van Tilborg, On the inherent intractability of certain coding problems, IEEE Trans. Inform. Theory 24(3) (1978) 384–386.
D. J. Bernstein, T. Lange, and C. Peters, Smaller decoding exponents: Ball-collision decoding, in: Advances in Cryptology – CRYPTO 2011, Lecture Notes in Comput. Sci., vol. 6841, Springer, Berlin, Heidelberg (2011) 743–760.
J. Bolkema, H. Gluesing-Luerssen, C. A. Kelley, K. E. Lauter, B. Malmskog, and J. Rosenthal, Variations of the McEliece cryptosystem, in: Algebraic Geometry for Coding Theory and Cryptography, Assoc. Women Math. Ser., vol. 9, Springer, Cham (2017) 129–150.
A. Canteaut and F. Chabaud, A new algorithm for finding minimum-weight words in a linear code: Application to McEliece's cryptosystem and to narrow-sense BCH codes of length $511$, IEEE Trans. Inform. Theory 44(1) (1998) 367–378.
A. Canteaut and N. Sendrier, Cryptanalysis of the original McEliece cryptosystem, in: Advances in Cryptology – ASIACRYPT '98, Lecture Notes in Comput. Sci., vol. 1514, Springer, Berlin, Heidelberg (1998) 187–199.
F. Chabaud, Asymptotic analysis of probabilistic algorithms for finding short codewords, in: Eurocode '92, CISM Courses and Lectures, vol. 339, Springer, Vienna (1993) 175–183.
I. I. Dumer, Two decoding algorithms for linear codes, Problemy Peredachi Informatsii 25(1) (1989) 24–32; English translation: Probl. Inf. Transm. 25(1) (1989) 17–23.
M. Finiasz and N. Sendrier, Security bounds for the design of code-based cryptosystems, in: Advances in Cryptology – ASIACRYPT 2009, Lecture Notes in Comput. Sci., vol. 5912, Springer, Berlin, Heidelberg (2009) 88–105.
C. T. Gueye, J. B. Klamti, and S. Hirose, Generalization of BJMM-ISD using May-Ozerov nearest neighbor algorithm over an arbitrary finite field $\mathbb{F}_q$, in: Codes, Cryptology and Information Security, Lecture Notes in Comput. Sci., vol. 10194, Springer, Cham (2017) 96–109.
S. Hirose, May–Ozerov algorithm for nearest-neighbor problem over $\mathbb{F}_q$ and its application to information set decoding, in: Innovative Mobile and Internet Services in Ubiquitous Computing, Lecture Notes on Data Engineering and Communications Technologies, vol. 1, Springer, Cham (2016) 115–126.
N. Howgrave-Graham and A. Joux, New generic algorithms for hard knapsacks, in: Advances in Cryptology – EUROCRYPT 2010, Lecture Notes in Comput. Sci., vol. 6110, Springer, Berlin, Heidelberg (2010) 235–256.
K. Khathuria, J. Rosenthal, and V. Weger, Weight two masking of the Reed-Solomon structure in conjugation with list decoding, in: Proc. 23rd International Symposium on Mathematical Theory of Networks and Systems, Hong Kong (2018) 309–314.
E. A. Kruk, Decoding complexity bound for linear block codes, Probl. Peredachi Inf. 25(3) (1989) 103–107; English translation: Probl. Inf. Transm. 25(3) (1989) 254–258.
P. J. Lee and E. F. Brickell, An observation on the security of McEliece's public-key cryptosystem, in: Advances in Cryptology – EUROCRYPT '88, Lecture Notes in Comput. Sci., vol. 330, Springer, Berlin, Heidelberg (1988) 275–280.
J. S. Leon, A probabilistic algorithm for computing minimum weights of large error-correcting codes, IEEE Trans. Inform. Theory 34(5) (1988) 1354–1359.
A. May, A. Meurer, and E. Thomae, Decoding random linear codes in $\mathcal{O}(2^{0.054n})$, in: Advances in Cryptology – ASIACRYPT 2011, Lecture Notes in Comput. Sci., vol. 7073, Springer, Heidelberg (2011) 107–124.
A. May and I. Ozerov, On computing nearest neighbors with applications to decoding of binary linear codes, in: Advances in Cryptology – EUROCRYPT 2015, Lecture Notes in Comput. Sci., vol. 9056, Springer, Berlin, Heidelberg (2015) 203–228.
R. J. McEliece, A Public-Key Cryptosystem Based on Algebraic Coding Theory, DSN Progress Report 42-44, Jet Propulsion Laboratory, Pasadena, CA (1978) 114–116.
A. Meurer, A coding-theoretic approach to cryptanalysis, Ph.D. Thesis, Ruhr-Universität Bochum (2012).
R. Niebuhr, E. Persichetti, P.-L. Cayrel, S. Bulygin, and J. Buchmann, On lower bounds for information set decoding over $\mathbb{F}_q$ and on the effect of partial knowledge, Int. J. Inf. Coding Theory 4(1) (2017) 47–78.
C. Peters, Information-set decoding for linear codes over $\mathbb{F}_q$, in: Post-Quantum Cryptography, Lecture Notes in Comput. Sci., vol. 6061, Springer, Berlin, Heidelberg (2010) 81–94.
E. Prange, The use of information sets in decoding cyclic codes, IRE Trans. Inform. Theory 8(5) (1962) 5–9.
A. Schönhage and V. Strassen, Schnelle Multiplikation großer Zahlen, Computing 7(3-4) (1971) 281–292.
J. Stern, A new identification scheme based on syndrome decoding, in: Advances in Cryptology – CRYPTO '93, Lecture Notes in Comput. Sci., vol. 773, Springer, Berlin, Heidelberg (1994) 13–21.
J. van Tilburg, On the McEliece public-key cryptosystem, in: Advances in Cryptology – CRYPTO '88, Lecture Notes in Comput. Sci., vol. 403, Springer, New York (1990) 119–131.
