One-Way Functions Are Essential for Single-Server Private Information Retrieval.

Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tal Malkin

Browse the full STOC paper archive.