Managing the Noise in Homomorphic Encryption
homomorphic encryption, noise growth
Beschreibung
Background
Homomorphic Encryption (HE) is a powerful cryptographic paradigm that allows computations to be performed directly on encrypted data, without ever needing to decrypt it first. The result of such a computation, once decrypted, is identical to what would have been obtained by performing the same operation on the plaintext. This makes HE particularly attractive for privacy-preserving applications in cloud computing, medical data analysis, and machine learning, where sensitive data must be processed by an untrusted third party.
The Noise Problem
Modern HE schemes — such as BGV, BFV, and CKKS — are built on the hardness of lattice problems, most notably Learning With Errors (LWE) and its ring variant (RLWE). The security of these schemes relies on the presence of noise in ciphertexts. However, homomorphic operations cause this noise to grow. Left unchecked, this noise growth quickly renders ciphertexts undecryptable, fundamentally limiting the depth and complexity of computations that can be performed. Noise management is therefore a central challenge in practical HE.
Internship Task
Several techniques have been developed to control or reduce noise growth in HE schemes, such as bootstrapping, modulus switching, flattening and rescaling.
In this internship, the student will try to develop a new noise management technique. The student will then compare this new technique to the existing ones, compare their computational costs and performance. The student will complement this with practical experiments using established HE libraries.
References
[1] Gentry, C. "Fully Homomorphic Encryption Using Ideal Lattices." Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 169–178, 2009.
[2] Brakerski, Z. and Vaikuntanathan, V. "Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages." Advances in Cryptology – CRYPTO 2011, Lecture Notes in Computer Science, vol. 6841, Springer, 2011.
[3] Brakerski, Z., Gentry, C., and Vaikuntanathan, V. "(Leveled) Fully Homomorphic Encryption without Bootstrapping." Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS), pp. 309–325, 2012.
[4] Fan, J. and Vercauteren, F. "Somewhat Practical Fully Homomorphic Encryption." Cryptology ePrint Archive, Report 2012/144, 2012.
[5] Cheon, J. H., Kim, A., Kim, M., and Song, Y. "Homomorphic Encryption for Arithmetic of Approximate Numbers." Advances in Cryptology – ASIACRYPT 2017, Lecture Notes in Computer Science, vol. 10624, Springer, pp. 409–437, 2017.
[6] Gentry, C., Sahai, A., and Waters, B. "Homomorphic Encryption from Learning with Errors: Conceptually Simpler, Asymptotically Faster, Attribute-Based." Advances in Cryptology – CRYPTO 2013, Lecture Notes in Computer Science, vol. 8042, Springer, pp. 75–92, 2013.
Betreuer:
Noise Management Techniques in Homomorphic Encryption
homomorphic encryption, noise growth
Beschreibung
Background
Homomorphic Encryption (HE) is a powerful cryptographic paradigm that allows computations to be performed directly on encrypted data, without ever needing to decrypt it first. The result of such a computation, once decrypted, is identical to what would have been obtained by performing the same operation on the plaintext. This makes HE particularly attractive for privacy-preserving applications in cloud computing, medical data analysis, and machine learning, where sensitive data must be processed by an untrusted third party.
The Noise Problem
Modern HE schemes — such as BGV, BFV, and CKKS — are built on the hardness of lattice problems, most notably Learning With Errors (LWE) and its ring variant (RLWE). The security of these schemes relies on the presence of noise in ciphertexts. However, homomorphic operations cause this noise to grow. Left unchecked, this noise growth quickly renders ciphertexts undecryptable, fundamentally limiting the depth and complexity of computations that can be performed. Noise management is therefore a central challenge in practical HE.
Internship Task
Several techniques have been developed to control or reduce noise growth in HE schemes, such as bootstrapping, modulus switching, flattening and rescaling.
In this internship, the student will conduct a structured investigation of noise management techniques in homomorphic encryption. The goal is to develop a thorough and hands-on understanding of the state of the art. Concretely, the student will survey the techniques described above, study their theoretical underpinnings, compare their computational costs and noise behavior across different HE schemes (e.g., BGV, BFV, CKKS), and ideally complement this with practical experiments using an established HE library such as Microsoft SEAL or OpenFHE.
References
[1] Gentry, C. "Fully Homomorphic Encryption Using Ideal Lattices." Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 169–178, 2009.
[2] Brakerski, Z. and Vaikuntanathan, V. "Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages." Advances in Cryptology – CRYPTO 2011, Lecture Notes in Computer Science, vol. 6841, Springer, 2011.
[3] Brakerski, Z., Gentry, C., and Vaikuntanathan, V. "(Leveled) Fully Homomorphic Encryption without Bootstrapping." Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS), pp. 309–325, 2012.
[4] Fan, J. and Vercauteren, F. "Somewhat Practical Fully Homomorphic Encryption." Cryptology ePrint Archive, Report 2012/144, 2012.
[5] Cheon, J. H., Kim, A., Kim, M., and Song, Y. "Homomorphic Encryption for Arithmetic of Approximate Numbers." Advances in Cryptology – ASIACRYPT 2017, Lecture Notes in Computer Science, vol. 10624, Springer, pp. 409–437, 2017.
[6] Gentry, C., Sahai, A., and Waters, B. "Homomorphic Encryption from Learning with Errors: Conceptually Simpler, Asymptotically Faster, Attribute-Based." Advances in Cryptology – CRYPTO 2013, Lecture Notes in Computer Science, vol. 8042, Springer, pp. 75–92, 2013.
Betreuer:
Upper Bounds on Integer Partitions
combinatorics, number theory, sum-rank metric
Beschreibung
How many ways are there to write down n nonnegative integers, all of which being strictly smaller than q, such that their sum is k? In other words, what is the coefficient of x^k in (1 + x + ... + x^(q-1))^n?
In this thesis, we are going to dive into the integer partitioning problem with a certain number of partitions and an upper bound on partition size.
The goal of this thesis is to take an already existing bound for the value mentioned above, which holds for a specific k value - and extend it to general k.
The upper bound can then be used for proving better upper bounds in coding theory for certain metrics other than the Hamming metric.
[1] H. B.-S. Couvée, T. Jerkovits, and J. Bariffi, ‘Bounds on Sphere Sizes in the Sum-Rank Metric and Coordinate-Additive Metrics’, Des. Codes Cryptogr., Mar. 2025, doi: 10.1007/s10623-025-01604-0.
Voraussetzungen
information theory, channel coding, strong interest in combinatorics and number theory
Betreuer:
Attaining Fully Homomorphic Encryption through Private Information Retrieval
homomorphic encryption, learning with errors, private information retrieval
Beschreibung
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
Security in Communications and Storage