Due to the recent advances in quantum computers, searching for cryptosystems that survive quantum attacks is of great interest. Code-based cryptography is a promising candidate, which is built on the hardness of the syndrome decoding problem (SDP) [4].

Currently, the most efficient solvers for SDP are Information-Set Decoding (ISD) algorithms; see, e.g., [5].

The development of improved ISD algorithms has always been directly connected to the development of improved solvers for lattice problems.

A typical example includes the integration of nearest-neighbor techniques, which first appeared in the context of codes [6], and for lattices soon after [7].

The goal of this topic is the analysis of recently developed solvers for SDP [1-3] that are heavily inspired by solvers for lattice problems. As part of the project, these algorithms should be analyzed, and compared with their lattice counterparts.

**Main Papers:**

[1] Ghentiyala, S., & Stephens-Davidowitz, N. (2024). More basis reduction for linear codes: backward reduction, BKZ, slide reduction, and more. *arXiv preprint arXiv:2408.08507*.

[2] Debris-Alazard, T., Ducas, L., & van Woerden, W. P. (2022). An algorithmic reduction theory for binary codes: LLL and more. *IEEE Transactions on Information Theory*, *68*(5), 3426-3444.

[3] Ducas, L., Esser, A., Etinski, S., & Kirshanova, E. (2024, April). Asymptotics and improvements of sieving for codes. In *Annual International Conference on the Theory and Applications of Cryptographic Techniques* (pp. 151-180). Cham: Springer Nature Switzerland.

**References:**

[4] Weger, V., Gassner, N., & Rosenthal, J. (2022). A Survey on Code-Based Cryptography. *arXiv preprint arXiv:2201.07119*.

[5] May, A., Meurer, A., & Thomae, E. (2011, December). Decoding random linear codes in. In *International Conference on the Theory and Application of Cryptology and Information Security* (pp. 107-124). Berlin, Heidelberg: Springer Berlin Heidelberg.

[6] May, A., & Ozerov, I. (2015, April). On computing nearest neighbors with applications to decoding of binary linear codes. In *Annual International Conference on the Theory and Applications of Cryptographic Techniques* (pp. 203-228). Berlin, Heidelberg: Springer Berlin Heidelberg.

[7] Becker, A., Ducas, L., Gama, N., & Laarhoven, T. (2016). New directions in nearest neighbor searching with applications to lattice sieving. In *Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms* (pp. 10-24). Society for Industrial and Applied Mathematics.