Abstract:
We show that any 1-round 2-server Private Information Retrieval Protocol where the answers are 1-bit long must ask questions that are at least $n-2$ bits long, which is nearly equal to the known $n-1$ upper bound. This improves upon the approximately $0.25n$ lower bound of Kerenidis and de Wolf while avoiding their use of quantum techniques.

Comment #1 to TR03-087 | 7th May 2006 13:43

Much cleaner version of ``A Nearly Tight Bound for PIR Retrieval Protocols" Comment on: TR03-087

Abstract:
This is a much cleaner version of ``A Nearly Tight Bound for PIR Retrieval Protocols". Readers are strongly encouraged to read this version, not the one originally posted. The new version is in Computational Complexity, Vol 15, No 1, 2006, 82--91.