Generalization of the Ball-Collision Algorithm
From MaRDI portal
Publication:5855596
zbMATH Open1468.94462arXiv1812.10955MaRDI QIDQ5855596FDOQ5855596
Violetta Weger, Joachim Rosenthal, J. Carmelo Interlando, Nicole Rohrer, Karan Khathuria
Publication date: 19 March 2021
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.
Full work available at URL: https://arxiv.org/abs/1812.10955
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fast multiplication of large numbers
- Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding
- Decoding Random Linear Codes in $\tilde{\mathcal{O}}(2^{0.054n})$
- Information-Set Decoding for Linear Codes over F q
- Security Bounds for the Design of Code-Based Cryptosystems
- A probabilistic algorithm for computing minimum weights of large error-correcting codes
- 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
- Minimal vectors in linear codes
- Smaller Decoding Exponents: Ball-Collision Decoding
- Enhanced public key security for the McEliece cryptosystem
- On the inherent intractability of certain coding problems (Corresp.)
- A new identification scheme based on syndrome decoding
- New Generic Algorithms for Hard Knapsacks
- On the complexity of minimum distance decoding of long linear codes
- DAGS: key encapsulation using dyadic GS codes
- On lower bounds for information set decoding over \(\mathbb F_q\) and on the effect of partial knowledge
- On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes
- Two decoding algorithms for linear codes
- Variations of the McEliece cryptosystem
- A Statistical Decoding Algorithm for General Linear Block Codes
- Generalization of BJMM-ISD Using May-Ozerov Nearest Neighbor Algorithm over an Arbitrary Finite Field $$\mathbb {F}_q$$
Cited In (11)
- Information set decoding in the Lee metric with applications to cryptography
- On the design and security of Lee metric McEliece cryptosystems
- An algorithm for generalized syndrome decoding problem
- Improved Generic Algorithms for 3-Collisions
- S-semantics -- an example
- Information-set decoding with hints
- On the hardness of the Lee syndrome decoding problem
- Another generalization of the box–ball system with many kinds of balls
- Theoretical analysis of decoding failure rate of non-binary QC-MDPC codes
- Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems
- Improved information set decoding algorithms over Galois ring in the Lee metric
Uses Software
This page was built for publication: Generalization of the Ball-Collision Algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5855596)
