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

Source: [List-Decodable Byzantine Robust PIR: Lower Communication Complexity, Higher Byzantine Tolerance, Smaller List Size](<https://www.sota2.com/research/paper/68fa798d1e209131cea7e2a8>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-04-03T05:00:04.568Z

Authors: Pengzhen Ke, Liang Feng Zhang, Huaxiong Wang, Li-Ping Wang

Published: 2025-06-21T07:52:24.000Z

## 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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [List-Decodable Byzantine Robust PIR on Database (n=2^16, k=6, b=3, t=1, log\|Fp\|=7)](<https://www.sota2.com/research/sota/list-decodable-byzantine-robust-pir-on-database-n-2-16-k-6-b-3-t-1-log-fp-7.md>): List-Decodable Byzantine Robust PIR; Database (n=2^16, k=6, b=3, t=1, log\|Fp\|=7); Worst List Size: 2.

- [List-Decodable Byzantine Robust PIR on Database (n=2^16, k=6, b=3, t=1, log\|Fp\|=10)](<https://www.sota2.com/research/sota/list-decodable-byzantine-robust-pir-on-database-n-2-16-k-6-b-3-t-1-log-fp-10.md>): List-Decodable Byzantine Robust PIR; Database (n=2^16, k=6, b=3, t=1, log\|Fp\|=10); Worst List Size: 2.

- [Byzantine-robust Private Information Retrieval on Database in F\_p^n](<https://www.sota2.com/research/sota/byzantine-robust-private-information-retrieval-on-database-in-f_p-n.md>): Byzantine-robust Private Information Retrieval; Database in F\_p^n; Communication Complexity (Big O): 1.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2506.17625>)

[PDF](<https://arxiv.org/pdf/2506.17625.pdf>)
