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.

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). Every ciphertext carries a small amount of noise, which is what makes the scheme hard to break but also what makes decryption imperfect and what grows with every homomorphic operation performed on the ciphertext. Managing this noise is the central practical bottleneck of HE.

The HE-Specific Gap

The research internship on this topic surveys how coding can close part of the gap between the uncoded message rate and the capacity of the LWE/MLWE channel — but only for a single, fresh ciphertext, exactly as in the PKE/KEM setting the two survey papers study. Fully Homomorphic Encryption is different in a way neither paper addresses: a scheme is standardly run as a leveled circuit of some fixed target multiplicative depth D, followed by bootstrapping, and the noise a packed message actually faces is not the noise of a single encryption but the accumulated result of D homomorphic operations. Moreover, whatever encoding is used to pack the message must remain meaningful throughout — homomorphic addition and multiplication act algebraically on the encoded plaintext directly, so an error-correcting code layered on top of the message has to commute with those operations, or be explicitly designed around what they do to it. Neither constraint has a counterpart in the PKE/KEM literature, where the ciphertext is decoded immediately after a single noisy hop.

Thesis Task

Building on the internship's survey, the student will investigate the depth-D LWE/ channel under the additional constraint that the message encoding must commute with homomorphic addition and multiplication. Rather than aiming directly for an explicit optimal code — which the homomorphism-compatibility constraint makes considerably harder to construct than the codes surveyed in the internship — the student will approach the problem from a bounds perspective:

• characterize the channel faced by a packed message at a fixed target depth D, extending the existing capacity results for the fresh-ciphertext LWE channel to this accumulated-noise setting;
• formalize the class of homomorphism-compatible encoders (e.g., module or ring homomorphisms into the plaintext space) and derive achievability and converse bounds on the best rate attainable within this constrained class, in the spirit of structured-coding results such as Körner–Marton and compute-and-forward;
• quantify the resulting gap between this constrained capacity and the unconstrained channel capacity, to establish how much rate is fundamentally given up for homomorphism-compatibility alone;
• where possible, check whether simple existing constructions (e.g., linear or CRT/SIMD-based plaintext packing already used in BGV/BFV) approach the derived bound

References

[1] Regev, O. "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography." STOC, 2005.

[2] Maringer, G. and Wachter-Zeh, A. "Reducing Ciphertext and Key Sizes for MLWE-Based Cryptosystems." arXiv:2502.01339, 2025.

[3] Lee, E., Kim, Y.-S., No, J.-S., Song, M., and Shin, D.-J. "Modification of FrodoKEM Using Gray and Error-Correcting Codes." IEEE Access, vol. 7, pp. 179564–179574, 2019.

[4] Maringer, G., Puchinger, S., and Wachter-Zeh, A. "Information- and Coding-Theoretic Analysis of the RLWE/MLWE Channel." IEEE Transactions on Information Forensics and Security, vol. 18, pp. 549–564, 2022.

[5] Gentry, C. "Fully Homomorphic Encryption Using Ideal Lattices." STOC, pp. 169–178, 2009.

[6] Brakerski, Z., Gentry, C., and Vaikuntanathan, V. "(Leveled) Fully Homomorphic Encryption without Bootstrapping." ITCS, pp. 309–325, 2012.

[7] Körner, J. and Marton, K. "How to Encode the Modulo-Two Sum of Binary Sources." IEEE Transactions on Information Theory, vol. 25, no. 2, pp. 219–221, 1979.

[8] Nazer, B. and Gastpar, M. "Compute-and-Forward: Harnessing Interference Through Structured Codes." IEEE Transactions on Information Theory, vol. 57, no. 10, pp. 6463–6486, 2011.

[9] Lyu, S., Liu, L., Ling, C., Lai, J., and Chen, H. "Lattice Codes for Lattice-Based PKE." Designs, Codes and Cryptography, 2023.

Voraussetzungen

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 theis, 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.

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.

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

How can two parties exchange secrets so that one learns exactly what they need, while the other remains completely “oblivious”? This is the intriguing idea behind Oblivious Transfer (OT), one of cryptography’s most fundamental building blocks.

In this seminar, you will trace OT from its origins in the early days of public-key cryptography to its role as a cornerstone of secure computation. The goal is to understand the core ideas, why OT is so powerful, and how it shapes modern cryptographic protocols. 

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] S. Even, O. Goldreich, and A. Lempel, “A randomized protocol for signing contracts,” Commun. ACM, vol. 28, pp. 637–647, 01 1985.

Voraussetzungen

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.

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). Every ciphertext carries a small amount of noise, which is what makes the scheme hard to break but also what makes decryption imperfect and what grows with every homomorphic operation performed on the ciphertext. Managing this noise is the central practical bottleneck of HE.

The Channel Perspective

LWE-based encryption can be read as a point-to-point communication channel: encryption maps a message onto a small constellation embedded in Z_q, the LWE noise term plays the role of channel noise, and decryption is nearest-neighbor decoding — the maximum-likelihood detector for that channel. Under this reading, "noise budget" becomes channel capacity, "decryption failure rate" becomes decoding error probability, and noise growth under homomorphic operations becomes a channel whose capacity shrinks with circuit depth. This connects HE directly to classical results in coding and information theory, largely independently of how the HE literature currently manages noise.

Internship Task

In this internship, the student will conduct a structured investigation of noise management in HE viewed through this communication-theoretic lens. Concretely, the student will:

• formalize the channel model underlying symmetric-key LWE-based encryption, and derive the resulting decoding-error and capacity expressions;

• survey how the coding-theory and cryptography literature already touches this picture — error-correcting and lattice-coded message encodings, reconciliation techniques, decryption-failure analyses — and connect these back to the channel framing. Two papers provided as part of this internship illustrate exactly this: one applies BCH codes together with finite-blocklength achievability bounds to an MLWE-based scheme resembling Kyber, the other applies Gray-coded BCH codes to FrodoKEM. Working through both, the student will place their achieved rates and decryption failure rates explicitly against the channel's capacity, to see how much of the gap between the uncoded and capacity-achieving rate these constructions actually close;
• compare, across BGV, BFV, and CKKS, how each scheme's noise growth under homomorphic operations reads as a depletion of channel capacity with circuit depth;

References

[1] Regev, O. "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography." Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), 2005.

[2] Fritzmann, T., Pöppelmann, T., and Sepúlveda, J. "Analysis of Error-Correcting Codes for Lattice-Based Key Exchange." Selected Areas in Cryptography (SAC) 2018 / Cryptology ePrint Archive, Report 2018/150.

[3] D'Anvers, J.-P., Vercauteren, F., and Verbauwhede, I. "On the Impact of Decryption Failures on the Security of LWE/LWR Based Schemes." PQCrypto 2019 / Cryptology ePrint Archive, Report 2018/1089.

[4] Lyu, S., Liu, L., Ling, C., Lai, J., and Chen, H. "Lattice Codes for Lattice-Based PKE." Designs, Codes and Cryptography, 2023 / Cryptology ePrint Archive, Report 2022/874.

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

[6] Fan, J. and Vercauteren, F. "Somewhat Practical Fully Homomorphic Encryption." Cryptology ePrint Archive, Report 2012/144, 2012.

[7] Cheon, J. H., Kim, A., Kim, M., and Song, Y. "Homomorphic Encryption for Arithmetic of Approximate Numbers." Advances in Cryptology – ASIACRYPT 2017, LNCS vol. 10624, Springer, pp. 409–437, 2017.

[8] Maringer, G. and Wachter-Zeh, A. "Reducing Ciphertext and Key Sizes for MLWE-Based Cryptosystems." arXiv:2502.01339, 2025.

[9] Lee, E., Kim, Y.-S., No, J.-S., Song, M., and Shin, D.-J. "Modification of FrodoKEM Using Gray and Error-Correcting Codes." IEEE Access, vol. 7, pp. 179564–179574, 2019.

Voraussetzungen