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

Private Information Retrieval (PIR) is the problem of retrieving a desired data from a server/s while preventing the server from finding out the retrieved data. The scenario we consider has two additional constraints. Firstly, there is only a single server to retrieve the data from, and secondly, the retrievers should remain oblivious to the data they are not initially interested in.

The task of the student is to understand comparatively analyze the proposed approaches to this problem in [1] and [2].

References:

[1] E. Kushilevitz and R. Ostrovsky. Replication is not needed: single database, computationally-private information retrieval. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, FOCS ’97, page 364, USA, 1997. IEEE Computer Society

[2] Carlos AGUILAR MELCHOR and Philippe GABORIT. A lattice-based computationally-efficient
private information retrieval protocol. Cryptology ePrint Archive, Paper 2007/446, 2007.

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