Due to the recent advances in quantum computers, searching for cryptosystems that survive quantum attacks is of great interest. Lattice- and code-based hardness assumptions are promising candidates, both of which are built on the hardness of solving noisy linear equations [3].

The close relationship between codes and lattices has contributed to advances in both research areas: state-of-the-art solvers employ similar techniques (see, e.g. [4]), and constructions often follow analogous approaches (see, e.g. [5]).
However, not all lattice (or code) concepts currently have couterparts in the other domain.

In this thesis, the concepts of Learning with Rounding (LWR) [1] and Learning with Quantization (LWQ) [2] are applied to codes.
The LWR and LWQ problems are variants of the Learning with Errors (LWE) problem on lattices, where the small error ensuring the hardness of the problem, is replaced by a deterministic rounding or quantization procedure. Due to the similarity of the lattice-based LWE problem and the code-based Syndrome Decoding (SD) problem, it should be investigated, if the reductions from LWE to LWR and LWQ can be transferred to the SD problem, introducing the concept of Syndrome Decoding with Rounding for codes, and how this can be used in code-based cryptography.

Main Papers:

[1] Alwen, J., Krenn, S., Pietrzak, K., & Wichs, D. (2013, August). Learning with rounding, revisited: New reduction, properties and applications. In Annual Cryptology Conference (pp. 57-74). Berlin, Heidelberg: Springer Berlin Heidelberg.

[2] Lyu, S., Liu, L., & Ling, C. (2024). Learning with Quantization, Polar Quantizer, and Secure Source Coding. Cryptology ePrint Archive.

References:

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

[4] 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.

[5] Melchor, C. A., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J. C., ... & Bourges, I. C. (2018). Hamming quasi-cyclic (HQC). NIST PQC Round, 2(4), 13.

A homomorphic encryption (HE) scheme enables performing operations on plaintexts in their encrypted form. [1] A somewhat HE scheme supports both additions and multiplication, however up to a certain number of either of them. In comparison, a fully HE scheme supports an infinite number of additions and multiplications to be performed.

Nowadays, many of the efficient HE schemes are based on lattices, i.e. the Euclidean metric. Although different metrics can be used to construct HE schemes, such as the rank metric and the Hamming metric.

The goal of this research internship is to investigate the somewhat HE scheme presented in [1], which is based on the rank metric. Following that, the student should compare the scheme to other schemes based on other metrics, such as the one in [2] based on the Hamming metric, and the ones in [3], [4], [5], based on the Euclidean metric.

References:

[1] C. Aguilar-Melchor, V. Dyseryn, and P. Gaborit, ‘Somewhat Homomorphic Encryption based on Random Codes’, 2023, 2023/1798. Accessed: Oct. 09, 2024. [Online]. Available: https://eprint.iacr.org/2023/1798

[2] H. Corrigan-Gibbs, A. Henzinger, Y. Kalai, and V. Vaikuntanathan, ‘Somewhat Homomorphic Encryption from Linear Homomorphism and Sparse LPN’, 2024, 2024/1760. Accessed: Nov. 08, 2024. [Online]. Available: https://eprint.iacr.org/2024/1760

[3] Z. Brakerski and V. Vaikuntanathan, ‘Efficient Fully Homomorphic Encryption from (Standard) LWE’, in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, CA, USA: IEEE, Oct. 2011, pp. 97–106. doi: 10.1109/FOCS.2011.12.

[4] L. Ducas and D. Micciancio, ‘FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second’, in Advances in Cryptology -- EUROCRYPT 2015, E. Oswald and M. Fischlin, Eds., Berlin, Heidelberg: Springer, 2015, pp. 617–640. doi: 10.1007/978-3-662-46800-5_24.

[5] I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène, ‘TFHE: Fast Fully Homomorphic Encryption over the Torus’, 2018, 2018/421. Accessed: Nov. 08, 2024. [Online]. Available: https://eprint.iacr.org/2018/421

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.

Prerequisites