-

In single-server Private Information Retrieval (PIR), a server stores a database from which a user wants to download a specific entry.
While the database is public — allowing the user to learn additional entries — the server should not learn any information about which file the user is interested in.

This problem appears in numerous applications, such as safe browsing.
A trivial solution is downloading the entire database, which is, however, highly inefficient. Cryptographic techniques offer more practical solutions that significantly reduce communication costs.

This project will survey existing constructions for efficient single-server PIR. The goal is to categorize these constructions based on their underlying hardness assumptions, the use of preprocessing, and key techniques used. The project requires reading and understanding several references; a good starting point can be the following works:

[1] Zhou, Mingxun, et al. "Piano: extremely simple, single-server PIR with sublinear server computation." IEEE Symposium on Security and Privacy, 2024.

[2] Li, Baiyu, et al. "Hintless single-server private information retrieval." Annual International Cryptology Conference, 2024.

Prerequisites

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.