Generalization of the ball-collision algorithm

Abstract

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.

Keywords

• Coding theory,ISD,Ball-collision

References

1. [1] A. Al Jabri, A statistical decoding algorithm for general linear block codes, In IMA International Conference on Cryptography and Coding, pages 1–8, Springer, 2001.
2. [2] A. Ashikhmin, A. Barg, Minimal vectors in linear codes, IEEE Trans. Inform. Theory 44(5) (1998) 2010–2017.
3. [3] M. Baldi, M. Bianchi, F. Chiaraluce, J. Rosenthal, D. Schipani, Enhanced public key security for the McEliece cryptosystem, J. Cryptology 29 (2016) 1–27.
4. [4] G. Banegas, P. SLM Barreto, B. Odilon Boidje, P.-L. Cayrel, G. Ndollane Dione, K. Gaj, C. Thiécoumba Gueye, R. Haeussler, J. Belo Klamti, O. N’diaye, et al. DAGS: Key encapsulation using dyadic GS codes, J. Math. Cryptol. 12(4) (2018) 221–239.
5. [5] A. Barg, E. Krouk, 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.
6. [6] A. Becker, A. Joux, A. May, A. Meurer, Decoding random binary linear codes in 2n/20: How 1+ 1= 0 improves information set decoding, In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 520–536. Springer, 2012.
7. [7] E. Berlekamp, R. McEliece, H. van Tilborg, On the inherent intractability of certain coding problems (Corresp.), IEEE Trans. Inform. Theory 24(3) (1978) 384–386.
8. [8] D. J. Bernstein, T. Lange, C. Peters, Smaller decoding exponents: ball-collision decoding, In Annual Cryptology Conference, pages 743–760, Springer, 2011.

9. [9] J. Bolkema, H. Gluesing-Luerssen, C. A. Kelley, K. Lauter, B. Malmskog, J. Rosenthal. Variations of the McEliece Cryptosystem, In Algebraic Geometry for Coding Theory and Cryptography, pages 129–150. Springer, 2017.
10. [10] A. Canteaut, 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.
11. [11] A. Canteaut, N. Sendrier, Cryptanalysis of the original McEliece cryptosystem, In International Conference on the Theory and Application of Cryptology and Information Security, pages 187–199. Springer, 1998.
12. [12] F. Chabaud, Asymptotic analysis of probabilistic algorithms for finding short codewords, In Eurocode’ 92, pages 175–183, Springer, 1993.
13. [13] I. I. Dumer, Two decoding algorithms for linear codes, Problemy Peredachi Informatsii, 25(1) (1989) 24–32.
14. [14] M. Finiasz, N. Sendrier, Security bounds for the design of code-based cryptosystems, In International Conference on the Theory and Application of Cryptology and Information Security, pages 88–105, Springer, 2009.
15. [15] C. T. Gueye, J. B. Klamti, S. Hirose, Generalization of BJMM-ISD using May-Ozerov nearest neighbor algorithm over an arbitrary finite field $\mathbb{F}_q$, In Said El Hajji, Abderrahmane Nitaj, and El Mamoun Souidi, editors, Codes, Cryptology and Information Security, pages 96–109, Springer, 2017.
16. [16] S. Hirose, May–Ozerov algorithm for nearest-neighbor problem over $\mathbb{F}_q$ and its application to information set decoding, In International Conference for Information Technology and Communications, pages 115–126, Springer, 2016.
17. [17] N. Howgrave-Graham, A. Joux, New generic algorithms for hard knapsacks, In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 235–256. Springer, 2010.
18. [18] K. Khathuria, J. Rosenthal, V. Weger, Weight Two Masking of the Reed- Solomon Structure in Conjugation with List Decoding. In Proceedings of 23rd International Symposium on Mathematical Theory of Networks and Systems, pages 309–314, Hong Kong University of Science and Technology, Hong Kong, 2018.
19. [19] E. A. Kruk, Decoding complexity bound for linear block codes, Probl. Peredachi Inf. 25(3) (1989) 103–107.
20. [20] P. J. Lee, E. F. Brickell, An observation on the security of McEliece’s public-key cryptosystem, In Workshop on the Theory and Application of of Cryptographic Techniques, pages 275–280, Springer, 1988.
21. [21] J. S. Leon, A probabilistic algorithm for computing minimum weights of large error–correcting codes, IEEE Trans. Inform. Theory 34(5) (1988) 1354–1359.
22. [22] A. May, A. Meurer, E. Thomae, Decoding random linear codes in $\mathcal{O}(2^{0.054 n})$, In International Conference on the Theory and Application of Cryptology and Information Security, pages 107–124, Springer, 2011.
23. [23] A. May, I. Ozerov, On computing nearest neighbors with applications to decoding of binary linear codes, In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 203–228. Springer, 2015.
24. [24] R. J. McEliece, A Public-Key Cryptosystem Based on Algebraic Coding Theory, Technical report, DSN Progress report, Jet Propulsion Laboratory, Pasadena, 1978.
25. [25] A. Meurer, A coding-theoretic approach to cryptanalysis, PhD thesis, Bochum-Ruhr University, 2012.
26. [26] R. Niebuhr, E. Persichetti, P.-L. Cayrel, S. Bulygin, J. Buchmann, On lower bounds for information set decoding over Fq and on the effect of partial knowledge, Int. J. Inf. Coding Theory 4(1) (2017) 47–78.
27. [27] C. Peters, Information-set decoding for linear codes over Fq, In International Workshop on Post- Quantum Cryptography, pages 81–94, Springer, 2010.
28. [28] E. Prange, The use of information sets in decoding cyclic codes, IRE Transactions on Information Theory 8(5) (1962) 5–9.
29. [29] A. Schönhage, V. Strassen, Schnelle multiplikation großer zahlen, Computing 7(3) (1971) 281—292.
30. [30] J. Stern, A new identification scheme based on syndrome decoding, In Annual International Cryptology Conference, pages 13–21, Springer, 1993.
31. [31] J. van Tilburg, On the McEliece public-key cryptosystem, In Conference on the Theory and Application of Cryptography, pages 119–131, Springer, 1988.