A fully homomorphic encryption (FHE) scheme is an encryption scheme which enables performing arbitrary operations on plaintexts in their encrypted form.

Private Information Retrieval (PIR) is the problem of retrieving a desired data from a database while preventing the database server from finding out the retrieved data.

The goal of this thesis/project is to understand and analyze how to obtain FHE from any PIR scheme [1], [3].

References:

[1] S. Halevi, ‘Homomorphic Encryption’, Y. Lindell, Ed., in Information Security and Cryptography. Cham: Springer International Publishing, 2017, pp. 219–276. doi: 10.1007/978-3-319-57048-8_5.

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

[3] V. Vaikuntanathan, ‘Computing Blindfolded: New Developments in Fully Homomorphic Encryption’, in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, Oct. 2011, pp. 5–16. doi: 10.1109/FOCS.2011.98.

[4] ‘Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages’, in Lecture Notes in Computer Science, Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 505–524. doi: 10.1007/978-3-642-22792-9_29.

[5] Y. Ishai and A. Paskin, “Evaluating branching programs on encrypted data,” in TCC, ser. Lecture Notes in Computer Science, S. P. Vadhan, Ed., vol. 4392. Springer, 2007, pp. 575–594.

Voraussetzungen

Homomorphic Encryption is an encryption technique that allows computations to be performed directly on encrypted data [1][2][3]. This is particularly promising for cloud applications or data analysis where data privacy must be preserved.

Although fully homomorphic encryption has attracted significant research interest over the past years, current state-of-the-art schemes yet have little practical use due to their high computational cost and ciphertext sizes. Therefore, current research largely focuses on optimizing these algorithms to make them practically usable.

Existing fully homomorphic encryption schemes are all lattice-based, i.e. [3][4]. Those schemes are noise-based, meaning that their security relies on masking the plaintext with added noise. Unfortunately this noise is also the main reason for the large ciphertext size and therefor the high computational cost of homomorphic operations on those.

This thesis aims to explore how standard error-correcting codes [5] from communication engineering can be used to allow more promising parameter choices for existing homomorphic encryption schemes, and therefore could improve their ciphertext sizes and computation complexity. This could also be directly applied to certain applications, as i.e. existing Private Information Retrieval schemes as for example [6][7].

Prior experience with cryptography or error-correcting codes is beneficial but not strictly required—as long as there is strong interest in the topic. For example having attended a lecture on cryptography (e.g., Security in Communication and Storage) or coding theory (e.g., Channel Coding) is helpful.

[1] Rivest, Ronald L., Len Adleman, and Michael L. Dertouzos. "On data banks and privacy homomorphisms." Foundations of secure computation 4.11 (1978): 169-180.

[2] Vaikuntanathan, Vinod. "Computing blindfolded: New developments in fully homomorphic encryption." 2011 IEEE 52nd annual symposium on foundations of computer science. IEEE, 2011.

[3] Brakerski, Zvika. "Fundamentals of fully homomorphic encryption-a survey." Electronic Colloquium on Computational Complexity (ECCC). Vol. 25. 2018.

[4] Brakerski, Zvika, Craig Gentry, and Vinod Vaikuntanathan. "(Leveled) fully homomorphic encryption without bootstrapping." ACM Transactions on Computation Theory (TOCT), 2014.

[5] Gentry, Craig, Amit Sahai, and Brent Waters. "Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based." Advances in Cryptology–CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I. Springer Berlin Heidelberg, 2013.

[6] Roth, Ron. "Introduction to Coding Theory." Cambridge University Press, 2006.

[7] Henzinger, Alexandra, et al. "One server for the price of two: Simple and fast Single-Server private information retrieval." 32nd USENIX Security Symposium (USENIX Security 23). 2023.

[8] Gentry, Craig, and Shai Halevi. "Compressible FHE with applications to PIR." Theory of cryptography conference. Cham: Springer International Publishing, 2019.