Private information retrieval (PIR) is a key building block in many privacy-preserving systems, such as database querying, cloud computing and the Internet of Things. Homomorphic encryption (HE) is a promising solution for PIR. Although it has great potential, its practicality for keyword PIR is relatively low due to its high computational overhead. In this paper, we propose an efficient keyword PIR protocol called BCPIR, based on block code. In BCPIR, we design a new mapping scheme based on linear block codes that maps keywords to blocked binary strings with only one significant bit per block. Our block code can determine the distribution interval of significant bits and reduce the randomness of the significant bit distribution after mapping. In addition, based on block code, we preprocess the database and propose a novel keyword comparison method, which can support batch comparison and greatly improve the efficiency. We compare our solution to previous work and find that our solution is on average over 142 times faster for larger databases over 128MB. To further increase the utility of our solution, our scheme can be further accelerated on GPU. We test it on an A100 GPU and the overall performance can be increased by a further 10–20 times.

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

BCPIR: More Efficient Keyword PIR via Block Building Codewords

  • Shuquan Wang,
  • Hao Yang,
  • Lu Zhou

摘要

Private information retrieval (PIR) is a key building block in many privacy-preserving systems, such as database querying, cloud computing and the Internet of Things. Homomorphic encryption (HE) is a promising solution for PIR. Although it has great potential, its practicality for keyword PIR is relatively low due to its high computational overhead. In this paper, we propose an efficient keyword PIR protocol called BCPIR, based on block code. In BCPIR, we design a new mapping scheme based on linear block codes that maps keywords to blocked binary strings with only one significant bit per block. Our block code can determine the distribution interval of significant bits and reduce the randomness of the significant bit distribution after mapping. In addition, based on block code, we preprocess the database and propose a novel keyword comparison method, which can support batch comparison and greatly improve the efficiency. We compare our solution to previous work and find that our solution is on average over 142 times faster for larger databases over 128MB. To further increase the utility of our solution, our scheme can be further accelerated on GPU. We test it on an A100 GPU and the overall performance can be increased by a further 10–20 times.