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.

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.

Prerequisites

Oblivious transfer is a cryptographic protocol between a sender and a receiver. The server has multiple pieces of information, and according to which he/she has initially chosen, the receiver obtains only one of them. The sender remains oblivious to which information the receiver got.

Garbled circuits is the name of a cryptographic technique used for secure multi-party computation. It allows multiple parties to jointly compute a function on their private inputs, while preserving the privacy of the parties.

The task of the student is to understand the concept of garbled circuits ([4], [6]) based on oblivious transfer ([1], [2], [3], [5]).

References:

[1] W. Diffie and M. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654, November 1976.

[2] Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM, 26:96–99, 1978.

[3] Michael Rabin. How to exchange secrets with oblivious transfer. 1981.

[4] Andrew C. Yao. Protocols for secure computations. In 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pages 160–164, 1982.

[5] S. Even, O. Goldreich, and A. Lempel, “A randomized protocol for signing contracts,” Commun. ACM, vol. 28, pp. 637–647, 01 1985.

[6] Andrew Chi-Chih Yao. How to generate and exchange secrets. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pages 162–167, 198.

Prerequisites

A homomorphic encryption (HE) scheme enables performing operations on plaintexts in their encrypted form. Depending on its construction and constraints, an HE scheme can allow a limited or an unlimited number of operations, i.e. additions and/or multiplications.

The goal of this project is to investigate the scheme from [1] and to analyze its strengths and weaknesses to be able to adapt it for efficient implementations of specific operations such as dot product, vector-matrix multiplication and  linear combinations of vectors. Depending on the findings, the scheme can be applied for other operations as well.

References:

[1] C. Aguilar-Melchor, V. Dyseryn, and P. Gaborit, “Somewhat Homomorphic Encryption based on Random Codes,” 2023. Publication info: Preprint.