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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An Efficient Private Information Retrieval Protocol Based on TFHE

  • Haibo Tian,
  • Yini Lin

摘要

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.