Partial Server Side Parameter Selection in Private Information Retrieval
Thomas Vannet, Noboru Kunihiro · 2016
Over recent years, many Private Information Retrieval (PIR) schemes have been designed aiming for computational efficiency and overall real-world practicality. In particular, some preprocessing techniques have been studied to reach those goals. Our main contribution is a new preprocessing technique that reduces overall computation and communication and allows the client and server to share some of the computational burden without significantly reducing the security of the scheme and requires little to no additional space on the server's side. We show how this technique is naturally compatible with at least two schemes. One based on the Approximate GCD assumption and the other on the Ring-LWE problem. We provide theoretical complexities and show that in some cases we can achieve a less-than-n complexity in a single server PIR scheme for the first time through the combination of multiple optimization techniques.