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.
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.
