Homomorphic Encryption meets Error-Correcting Codes
Fully Homomorphic Encryption, Error-Correcting Codes, Lattice-based Cryptography
Description
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.
Supervisor:
Homomorphic Encryption
Homomorphic Encryption, GSW13
Description
Homomorphic Encryption (HE) is a type of encryption that allows calculations to be performed on the ciphertexts [1]. If any kind of operation is allowed, it is called Fully Homomorphic Encryption (FHE). This concept offers many opportunities regarding data protection for cloud services. This technology allows users to keep their data secret, while still being able to outsource calculations on this data to a server. For example, in the field of machine learning, the training can be carried out on private data.
The first fully homomorphic encryption system was introduced by Gentry in 2009 [2]. Since then, there have been various other schemes and optimizations. For a first overview [3] and [4] are recommended.
The goal of the seminar would be to give an overview of Homomorphic Encryption, including the variants and definitions, and to present a concrete instantiation of some FHE scheme, such as for example the GSW13 [5] or DGHV10 [6] scheme.
[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] Gentry, Craig. "Fully homomorphic encryption using ideal lattices." Proceedings of the forty-first annual ACM symposium on Theory of computing. 2009.
[3] Vaikuntanathan, Vinod. "Computing blindfolded: New developments in fully homomorphic encryption." 2011 IEEE 52nd annual symposium on foundations of computer science. IEEE, 2011.
[4] Brakerski, Zvika. "Fundamentals of fully homomorphic encryption-a survey." Electronic Colloquium on Computational Complexity (ECCC). Vol. 25. 2018.
[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] Van Dijk, Marten, et al. "Fully homomorphic encryption over the integers." Advances in Cryptology–EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30–June 3, 2010. Proceedings 29. Springer Berlin Heidelberg, 2010.
Supervisor:
Attaining Fully Homomorphic Encryption through Private Information Retrieval
homomorphic encryption, learning with errors, private information retrieval
Description
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
Security in Communications and Storage