Scholarlink

Private Information Retrieval (PIR) is a privacy-preserving primitive in cryptography. Significant endeavors have been made to address the variant of PIR concerning the malicious servers. Among those endeavors, list-decodable Byzantine robust PIR schemes may tolerate a majority of malicious responding servers that provide incorrect answers. In this paper, we propose two perfect list-decodable BRPIR schemes. Our schemes are the first ones that can simultaneously handle a majority of malicious responding servers, achieve a communication complexity of \( o(n^{1/2}) \) for a database of size n, and provide a nontrivial estimation on the list sizes. Compared with the existing solutions, our schemes attain lower communication complexity, higher Byzantine tolerance, and smaller list size.

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

List-Decodable Byzantine Robust PIR: Lower Communication Complexity, Higher Byzantine Tolerance, Smaller List Size

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Pengzhen Ke,
  • Liang Feng Zhang,
  • Huaxiong Wang,
  • Li-Ping Wang

摘要

Private Information Retrieval (PIR) is a privacy-preserving primitive in cryptography. Significant endeavors have been made to address the variant of PIR concerning the malicious servers. Among those endeavors, list-decodable Byzantine robust PIR schemes may tolerate a majority of malicious responding servers that provide incorrect answers. In this paper, we propose two perfect list-decodable BRPIR schemes. Our schemes are the first ones that can simultaneously handle a majority of malicious responding servers, achieve a communication complexity of \( o(n^{1/2}) \) for a database of size n, and provide a nontrivial estimation on the list sizes. Compared with the existing solutions, our schemes attain lower communication complexity, higher Byzantine tolerance, and smaller list size.