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.

Private Information Retrieval (PIR) is the problem of retrieving a desired data from a server while preventing the server from finding out the retrieved data.

Private Set Intersection (PSI) is the problem of multiple parties comparing their databases and computing the common elements, without revealing any information about the data they do not commonly possess.

The goal of this project is to understand both problems and to compare them. The main target is to design a protocol that can convert any PIR scheme to a PSI scheme and/or a protocol that can convert any PSI scheme to a PIR scheme.

References:

[1] Z. Wang, K. Banawan, and S. Ulukus, ‘Multi-Party Private Set Intersection: An Information-Theoretic Approach’, IEEE Journal on Selected Areas in Information Theory, vol. 2, no. 1, pp. 366–379, Mar. 2021, doi: 10.1109/JSAIT.2021.3057597.

[2] Z. Wang, K. Banawan, and S. Ulukus, ‘Private Set Intersection Using Multi-Message Symmetric Private Information Retrieval’, in 2020 IEEE International Symposium on Information Theory (ISIT), Jun. 2020, pp. 1035–1040. doi: 10.1109/ISIT44484.2020.9174221.

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. [1] A somewhat HE scheme supports both additions and multiplication, however up to a certain number of either of them. In comparison, a fully HE scheme supports an infinite number of additions and multiplications to be performed.

Nowadays, many of the efficient HE schemes are based on lattices, i.e. the Euclidean metric. Although different metrics can be used to construct HE schemes, such as the rank metric and the Hamming metric.

The goal of this research internship is to investigate the somewhat HE scheme presented in [1], which is based on the rank metric. Following that, the student should compare the scheme to other schemes based on other metrics, such as the one in [2] based on the Hamming metric, and the ones in [3], [4], [5], based on the Euclidean metric.

References:

[1] C. Aguilar-Melchor, V. Dyseryn, and P. Gaborit, ‘Somewhat Homomorphic Encryption based on Random Codes’, 2023, 2023/1798. Accessed: Oct. 09, 2024. [Online]. Available: https://eprint.iacr.org/2023/1798

[2] H. Corrigan-Gibbs, A. Henzinger, Y. Kalai, and V. Vaikuntanathan, ‘Somewhat Homomorphic Encryption from Linear Homomorphism and Sparse LPN’, 2024, 2024/1760. Accessed: Nov. 08, 2024. [Online]. Available: https://eprint.iacr.org/2024/1760

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

[4] L. Ducas and D. Micciancio, ‘FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second’, in Advances in Cryptology -- EUROCRYPT 2015, E. Oswald and M. Fischlin, Eds., Berlin, Heidelberg: Springer, 2015, pp. 617–640. doi: 10.1007/978-3-662-46800-5_24.

[5] I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène, ‘TFHE: Fast Fully Homomorphic Encryption over the Torus’, 2018, 2018/421. Accessed: Nov. 08, 2024. [Online]. Available: https://eprint.iacr.org/2018/421