|
Published Articles >> Table of Contents >> Abstract
47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
pp. 739-748
An \Omega(n^1/3 ) Lower Bound for Bilinear Group Based Private Information Retrieval
Alexander A. Razborov, IAS, Steklov Mathematical Institute
Sergey Yekhanin, MIT, USA
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.10
Send link to a friend
| Abstract |
|
A two server private information retrieval (PIR) scheme
allows a user U to retrieve the i-th bit of an n-bit string x
replicated between two servers while each server individually
learns no information about i. The main parameter
of interest in a PIR scheme is its communication complexity,
namely the number of bits exchanged by the user and
the servers. A large amount of effort has been invested
by researchers over the last decade in search for efficient
PIR schemes. A number of different schemes [6, 4, 19]
have been proposed, however all of them ended up with
the same communication complexity of O(n^{1/3}). The best
known lower bound to date is 5 log n by [17]. The tremendous
gap between upper and lower bounds is the focus of
our paper. We show an \Omega(n^{1/3}) lower bound in a restricted
model that nevertheless captures all known upper bound
techniques.
Our lower bound applies to bilinear group based PIR
schemes. A bilinear PIR scheme is a one round PIR scheme,
where user computes the dot product of servers’ responses
to obtain the desired value of the i-th bit. Every linear
scheme can be turned into a bilinear one with an asymptotically
negligible communication overhead. A group based
PIR scheme is a PIR scheme that involves servers representing
database by a function on a certain finite group
G, and allows user to retrieve the value of this function at
any group element using the natural secret sharing scheme
based on G. Our proof relies on representation theory of
finite groups.
|
 Additional Information
|
Citation:
Alexander A. Razborov, Sergey Yekhanin,
"An \Omega(n^1/3 ) Lower Bound for Bilinear Group Based Private Information Retrieval,"
focs,
pp. 739-748,
47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06),
2006
|
|
