Fully Homomorphic Encryption (FHE) enables computations on encrypted data without decryption, providing a powerful tool for privacy-preserving applications.

In this seminar, the student will study the BFV scheme, a widely used homomorphic encryption construction. The main goal is to understand the underlying mathematics, the design rationale of BFV, and how it fits into the broader landscape of lattice-based cryptography.

The student is expected to:

• Review the foundational works by Brakerski and by Fan–Vercauteren.
• Summarize the scheme’s construction, security assumptions, and noise management.
• Present connections to applications and implementations.

References:

[1] Z. Brakerski, "Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP," Advances in Cryptology – CRYPTO 2012, Lecture Notes in Computer Science, vol. 7417, Springer, 2012, pp. 868–886. doi: 10.1007/978-3-642-32009-5_50

[2] J. Fan and F. Vercauteren, "Somewhat Practical Fully Homomorphic Encryption," IACR Cryptology ePrint Archive, vol. 2012/144, 2012. Available:

Kalman filtering is one of the most prominent and widely used examples of estimation methods. The Kalman filter is a recursive algorithm that uses a series of measurements observed over time, containing statistical noise and other inaccuracies, to produce estimates of unknown variables.

It basically estimates the state of a dynamic system using a series of noisy measurements and operates in two steps: prediction, where it forecasts the next state using the system's model, and update, where it refines the estimate with new measurements.

This technique is widely applied in navigation, control systems, and signal processing for real-time data fusion and noise reduction. 

One of the main challenges in Kalman filtering, especially for privacy-preserving methods, is the inversion of matrices. To preserve privacy, computations can be done via homomorphic encryption. Homomorphic encryption is a form of encryption that allows computations to be performed directly on encrypted data without needing to decrypt it first.

For instance, the homomorphic evaluation of Kalman filters requires efficient matrix inversions, which can benefit from tailored homomorphic encryption methods. Effective privacy-preserving Kalman filtering can thus play a critical role in applications ranging from autonomous navigation and prediction of vehicle trajectories to financial modeling.

The goal of this project is to explore and implement efficient privacy-preserving techniques for statistical data analysis, with a focus on homomorphic evaluation of algorithms such as Kalman filters and clustering.

References:

[1] D. Simon, Optimal State Estimation: Kalman, H Infinity, and Nonlinear Approaches, Hoboken, NJ, USA: Wiley, 2006.

[2] M. S. Grewal and A. P. Andrews, Kalman Filtering: Theory and Practice Using MATLAB, 4th ed., Hoboken, NJ, USA: Wiley-IEEE Press, 2015.

[3] Z. Brakerski, ‘Fundamentals of fully homomorphic encryption’, in Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, New York, NY, USA: Association for Computing Machinery, 2019, pp. 543–563. Accessed: Oct. 22, 2024. [Online]. Available: https://doi.org/10.1145/3335741.3335762

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

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

Voraussetzungen

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.

Voraussetzungen

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.