Efficient Single Server Private Information Retrieval Without Preprocessing
摘要
Private Information Retrieval (PIR) enables clients to retrieve data from untrusted servers without disclosing the queried index, and single-server PIR is practical for real-world deployment as it avoids the non-collusion assumption among multiple servers. However, existing efficient single-server PIR schemes either rely on preprocessing (e.g., SimplePIR) or suffer from low throughput when handling small-sized data entries (e.g., Spiral). This paper proposes a novel preprocessing-free single-server PIR protocol optimized for dynamic databases with small-sized data entries. Our approach represents the database as a high-dimensional hypercube. We pack multiple small-sized entries into the coefficients of a single plaintext polynomial to the parallel computation of N entries using a single homomorphic multiplication. We adopt NTRU-based homomorphic encryption, replacing Regev’s encryption to reduce computational overhead. We design a new NTRUs-to-NTRU packing algorithm that aggregates multiple scalar NTRU ciphertexts. This packing strategy significantly reduces the number of computationally expensive external products required for high-dimensional retrieval. Our approach achieves a communication complexity of \(O(\log _N n)\) , robustly outperforming state-of-the-art schemes like Spiral, which have a communication complexity of \(O(\log _2 n)\) . Experimental results show that our scheme always bears the least communication cost and our scheme achieves higher throughput for databases with small-sized data entries (e.g., 1 B).