NewtonPIR: Communication Efficient Single-Server PIR
摘要
As a cryptographic primitive, private information retrieval (PIR) is extensively employed to ensure privacy protection. Although certain schemes realize communication costs unaffected by the database size N, they are still inefficient and hence unsuitable for practical deployment. This work introduces NewtonPIR, a single-server PIR construction optimized for communication efficiency. NewtonPIR can directly generate query values for the entire index without splitting the index and sending multiple query ciphertexts. NewtonPIR demonstrates 7.5 \(\times \) lower communication overhead than the state-of-the-art PIR scheme, with an additional 35.9 \(\sim \) 75 \(\times \) reduction compared to alternative approaches. 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.