| ||||
| ||||
![]() Title:NewtonPIR: Communication Efficient Single-Server PIR Conference:PRICAI 2025 Tags:Communication efficient, Homomorphic encryption and Single-server private information retrieval Abstract: Private information retrieval (PIR) is widely used for privacy protection. Although some schemes achieve communication overhead that is independent of the database size $N$, they remain inefficient and thus impractical for real-world use. In this paper, we propose NewtonPIR, a communication efficient single-server PIR scheme. NewtonPIR can directly generate query values for the entire index without splitting the index and sending multiple query ciphertexts. Specifically, NewtonPIR achieves communication overhead that is 7.5$\times$ better than the state-of-the-art PIR protocol and 35.9$\sim$75$\times$ better than the other protocols. In experiments, when the database size and entry size increase, the communication overhead of NewtonPIR remains stable. By utilizing the simple Newton interpolation polynomial and precomputing coefficients offline, we reduce the computation time from hours in the previous non-preprocessing scheme to seconds. Moreover, when new entries are added to the database, NewtonPIR performs incremental preprocessing of the interpolation coefficients without recomputing them from scratch. NewtonPIR: Communication Efficient Single-Server PIR ![]() NewtonPIR: Communication Efficient Single-Server PIR | ||||
| Copyright © 2002 – 2026 EasyChair |
