Research Article
An Efficient Private Information Retrieval Protocol Based on TFHE
@INPROCEEDINGS{10.1007/978-3-031-64948-6_24, author={Haibo Tian and Yini Lin}, title={An Efficient Private Information Retrieval Protocol Based on TFHE}, proceedings={Security and Privacy in Communication Networks. 19th EAI International Conference, SecureComm 2023, Hong Kong, China, October 19-21, 2023, Proceedings, Part I}, proceedings_a={SECURECOMM}, year={2024}, month={10}, keywords={private information retrieval fully homomorphic encryption over the torus simultaneous table lookup graphics processing units}, doi={10.1007/978-3-031-64948-6_24} }- Haibo Tian
Yini Lin
Year: 2024
An Efficient Private Information Retrieval Protocol Based on TFHE
SECURECOMM
Springer
DOI: 10.1007/978-3-031-64948-6_24
Abstract
Private Information Retrieval (PIR) allows a user to query an entry from a database without revealing the index of the entry to the database owner. It is a building tool for many privacy enhancement applications, such as compromised credential checking and stock value query. However, the efficiency of PIR protocols has always been a bottleneck in their practical deployment. To address the challenge, we propose leveraging the fully homomorphic encryption over the torus (TFHE) scheme, which supports implementation on 32-bit unsigned integers and features a fast controlled selector ((\textsf{CMux})) gate. The(\textsf{CMux})gate can naturally construct a table lookup algorithm to serve PIR. We introduce compression and expansion algorithms for a PIR query, resulting in an encrypted query only a few hundred bytes in size. Further, we present a parallel PIR protocol and four simultaneous table lookup (STLU) algorithms based on TFHE, which are implemented on graphics processing units (GPUs) and make a distributed PIR service with a fast response time. On four servers with five GPUs, we obtain a PIR service with a response time of less than 2 seconds and a query size of less than 200 bytes on a database containing(2^{22})entries, with each entry encoding a message of at least 256 bytes.
