Year 2020, Volume 7 , Issue 2, Pages 195 - 207 2020-05-07

Generalization of the ball-collision algorithm

Carmelo INTERLANDO [1] , Karan KHATHURIA [2] , Nicole ROHRER [3] , Joachim ROSENTHAL [4] , Violetta WEGER [5]


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.
Coding theory, ISD, Ball-collision
  • [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] A. Ashikhmin, A. Barg, Minimal vectors in linear codes, IEEE Trans. Inform. Theory 44(5) (1998) 2010–2017.
  • [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] 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] 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] 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] 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] D. J. Bernstein, T. Lange, C. Peters, Smaller decoding exponents: ball-collision decoding, In Annual Cryptology Conference, pages 743–760, Springer, 2011.
  • [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] 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] 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] F. Chabaud, Asymptotic analysis of probabilistic algorithms for finding short codewords, In Eurocode’ 92, pages 175–183, Springer, 1993.
  • [13] I. I. Dumer, Two decoding algorithms for linear codes, Problemy Peredachi Informatsii, 25(1) (1989) 24–32.
  • [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] 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] 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] 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] 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] E. A. Kruk, Decoding complexity bound for linear block codes, Probl. Peredachi Inf. 25(3) (1989) 103–107.
  • [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] 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] 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] 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] R. J. McEliece, A Public-Key Cryptosystem Based on Algebraic Coding Theory, Technical report, DSN Progress report, Jet Propulsion Laboratory, Pasadena, 1978.
  • [25] A. Meurer, A coding-theoretic approach to cryptanalysis, PhD thesis, Bochum-Ruhr University, 2012.
  • [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] C. Peters, Information-set decoding for linear codes over Fq, In International Workshop on Post- Quantum Cryptography, pages 81–94, Springer, 2010.
  • [28] E. Prange, The use of information sets in decoding cyclic codes, IRE Transactions on Information Theory 8(5) (1962) 5–9.
  • [29] A. Schönhage, V. Strassen, Schnelle multiplikation großer zahlen, Computing 7(3) (1971) 281—292.
  • [30] J. Stern, A new identification scheme based on syndrome decoding, In Annual International Cryptology Conference, pages 13–21, Springer, 1993.
  • [31] J. van Tilburg, On the McEliece public-key cryptosystem, In Conference on the Theory and Application of Cryptography, pages 119–131, Springer, 1988.
Primary Language en
Subjects Engineering
Journal Section Articles
Authors

Orcid: 0000-0003-4928-043X
Author: Carmelo INTERLANDO
Institution: San Diego State University
Country: Canada


Orcid: 0000-0002-9886-2770
Author: Karan KHATHURIA
Institution: University of Zurich
Country: Switzerland


Author: Nicole ROHRER
Institution: University of Zurich
Country: Switzerland


Orcid: 0000-0003-4545-3559
Author: Joachim ROSENTHAL
Institution: University of Zurich
Country: Switzerland


Orcid: 0000-0001-9186-2885
Author: Violetta WEGER
Institution: University of Zurich
Country: Switzerland


Dates

Publication Date : May 7, 2020

Bibtex @research article { jacodesmath729477, journal = {Journal of Algebra Combinatorics Discrete Structures and Applications}, issn = {}, eissn = {2148-838X}, address = {}, publisher = {Yildiz Technical University}, year = {2020}, volume = {7}, pages = {195 - 207}, doi = {10.13069/jacodesmath.729477}, title = {Generalization of the ball-collision algorithm}, key = {cite}, author = {Interlando, Carmelo and Khathurıa, Karan and Rohrer, Nicole and Rosenthal, Joachim and Weger, Violetta} }
APA Interlando, C , Khathurıa, K , Rohrer, N , Rosenthal, J , Weger, V . (2020). Generalization of the ball-collision algorithm . Journal of Algebra Combinatorics Discrete Structures and Applications , 7 (2) , 195-207 . DOI: 10.13069/jacodesmath.729477
MLA Interlando, C , Khathurıa, K , Rohrer, N , Rosenthal, J , Weger, V . "Generalization of the ball-collision algorithm" . Journal of Algebra Combinatorics Discrete Structures and Applications 7 (2020 ): 195-207 <https://dergipark.org.tr/en/pub/jacodesmath/issue/54201/729477>
Chicago Interlando, C , Khathurıa, K , Rohrer, N , Rosenthal, J , Weger, V . "Generalization of the ball-collision algorithm". Journal of Algebra Combinatorics Discrete Structures and Applications 7 (2020 ): 195-207
RIS TY - JOUR T1 - Generalization of the ball-collision algorithm AU - Carmelo Interlando , Karan Khathurıa , Nicole Rohrer , Joachim Rosenthal , Violetta Weger Y1 - 2020 PY - 2020 N1 - doi: 10.13069/jacodesmath.729477 DO - 10.13069/jacodesmath.729477 T2 - Journal of Algebra Combinatorics Discrete Structures and Applications JF - Journal JO - JOR SP - 195 EP - 207 VL - 7 IS - 2 SN - -2148-838X M3 - doi: 10.13069/jacodesmath.729477 UR - https://doi.org/10.13069/jacodesmath.729477 Y2 - 2020 ER -
EndNote %0 Journal of Algebra Combinatorics Discrete Structures and Applications Generalization of the ball-collision algorithm %A Carmelo Interlando , Karan Khathurıa , Nicole Rohrer , Joachim Rosenthal , Violetta Weger %T Generalization of the ball-collision algorithm %D 2020 %J Journal of Algebra Combinatorics Discrete Structures and Applications %P -2148-838X %V 7 %N 2 %R doi: 10.13069/jacodesmath.729477 %U 10.13069/jacodesmath.729477
ISNAD Interlando, Carmelo , Khathurıa, Karan , Rohrer, Nicole , Rosenthal, Joachim , Weger, Violetta . "Generalization of the ball-collision algorithm". Journal of Algebra Combinatorics Discrete Structures and Applications 7 / 2 (May 2020): 195-207 . https://doi.org/10.13069/jacodesmath.729477
AMA Interlando C , Khathurıa K , Rohrer N , Rosenthal J , Weger V . Generalization of the ball-collision algorithm. Journal of Algebra Combinatorics Discrete Structures and Applications. 2020; 7(2): 195-207.
Vancouver Interlando C , Khathurıa K , Rohrer N , Rosenthal J , Weger V . Generalization of the ball-collision algorithm. Journal of Algebra Combinatorics Discrete Structures and Applications. 2020; 7(2): 195-207.

Authors of the Article
Carmelo INTERLANDO [1]
Karan KHATHURIA [2]
Nicole ROHRER [3]
Joachim ROSENTHAL [4]
Violetta WEGER [5]