Private information retrieval: Three open problems (Short post)

  1. The Dvir-Gopi scheme requires superlinear server computation. Can you make it linear?

  2. In the 2-server information-theoretic setting, can we have a scheme with bandwidth and sublinear computation?

  3. Can we get doubly efficient PIR with servers?