Single-Server PIR via NTRU-Based FHE: Simpler, Smaller, and Faster

We introduce NTRU-PIR and NTRU-PIR-FREE, two single-server PIR protocols that offer new trade-offs in terms of storage, communication, and computation. Both of the protocols rely on the toolkit we developed for efficient homomorphic operations and ciphertext conversion algorithms on NTRU and an NTRU-based GSW-like scheme. Across a broad range of database configurations, NTRU-PIR simultaneously achieves a 1.5-26× reduction in public parameter size and a 1.7-4.2× increase in server throughput compared to previous counterparts. NTRU-PIR-FREE, a variant of NTRU-PIR by removing the query compression technique, eliminates the storage burden on the server. In the streaming setting, when the previous best-performing scheme Spiral-streampack(S&P 2022) reaches its highest throughput, NTRU-PIR-FREE achieves a comparable throughput with a query size of only 8 MB (compared to 30 MB for Spiralstreampack)and without requiring public parameters (compared to 125 MB for Spiralstreampack).