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

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Efficient Single Server Private Information Retrieval Without Preprocessing

  • Haohao Jiang,
  • Yi Qu,
  • Long Chen,
  • Min Zhang,
  • Xiaoyi Wang,
  • Dengguo Feng

摘要

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