International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Pengzhen Ke , School of Information Science and Technology, ShanghaiTech University, Shanghai, China
Liang Feng Zhang , School of Information Science and Technology, ShanghaiTech University, Shanghai, China; Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China
Huaxiong Wang , School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore
Li-Ping Wang , Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China
Download:
Search ePrint
Search Google
Conference: ASIACRYPT 2025
Abstract: 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.
BibTeX
@inproceedings{asiacrypt-2025-35948,
  title={List-Decodable Byzantine Robust PIR: Lower Communication Complexity, Higher Byzantine Tolerance, Smaller List Size},
  publisher={Springer-Verlag},
  author={Pengzhen Ke and Liang Feng Zhang and Huaxiong Wang and Li-Ping Wang},
  year=2025
}