Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with private information retrieval:
TR01-015 | 9th February 2001
Amos Beimel, Yuval Ishai

Information-Theoretic Private Information Retrieval: A Unified Construction

A Private Information Retrieval (PIR) protocol enables a user to
retrieve a data item from a database while hiding the identity of the
item being retrieved. In a $t$-private, $k$-server PIR protocol the
database is replicated among $k$ servers, and the user's privacy is
protected from any collusion of up ... more >>>

TR02-059 | 9th August 2002
Iordanis Kerenidis, Ronald de Wolf

Exponential Lower Bound for 2-Query Locally Decodable Codes

We prove exponential lower bounds on the length of 2-query
locally decodable codes. Goldreich et al. recently proved such bounds
for the special case of linear locally decodable codes.
Our proof shows that a 2-query locally decodable code can be decoded
with only 1 quantum query, and then ... more >>>

TR03-087 | 10th December 2003
Richard Beigel, Lance Fortnow, William Gasarch

A Nearly Tight Bound for Private Information Retrieval Protocols

Comments: 1

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

TR05-009 | 14th December 2004
David P. Woodruff, Sergey Yekhanin

A Geometric Approach to Information-Theoretic Private Information Retrieval

A t-private private information retrieval (PIR) scheme allows a user to retrieve the i-th bit of an n-bit string x replicated among k servers, while any coalition of up to t servers learns no information about i. We present a new geometric approach to PIR, and obtain (1) A t-private ... more >>>

TR06-050 | 18th April 2006
Alexander Razborov, Sergey Yekhanin

An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval

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

TR06-127 | 7th October 2006
Sergey Yekhanin

New Locally Decodable Codes and Private Information Retrieval Schemes

A q-query Locally Decodable Code (LDC) encodes an n-bit message
x as an N-bit codeword C(x), such that one can
probabilistically recover any bit x_i of the message
by querying only q bits of the codeword C(x), even after
some constant fraction of codeword bits has been corrupted.

We give ... more >>>

TR07-022 | 20th February 2007
Rafail Ostrovsky, William Skeith

Algebraic Lower Bounds for Computing on Encrypted Data

In cryptography, there has been tremendous success in building
primitives out of homomorphic semantically-secure encryption
schemes, using homomorphic properties in a black-box way. A few
notable examples of such primitives include items like private
information retrieval schemes and collision-resistant hash functions. In this paper, we illustrate a general
methodology for ... more >>>

TR08-069 | 5th August 2008
Klim Efremenko

3-Query Locally Decodable Codes of Subexponential Length

Locally Decodable Codes (LDC) allow one to decode any particular
symbol of the input message by making a constant number of queries
to a codeword, even if a constant fraction of the codeword is
damaged. In recent work ~\cite{Yekhanin08} Yekhanin constructs a
$3$-query LDC with sub-exponential length of size
$\exp(\exp(O(\frac{\log ... more >>>

TR10-173 | 9th November 2010
Yeow Meng Chee, Tao Feng, San Ling, Huaxiong Wang, Liang Feng Zhang

Query-Efficient Locally Decodable Codes

A $k$-query locally decodable code (LDC)
$\textbf{C}:\Sigma^{n}\rightarrow \Gamma^{N}$ encodes each message $x$ into
a codeword $\textbf{C}(x)$ such that each symbol of $x$ can be probabilistically
recovered by querying only $k$ coordinates of $\textbf{C}(x)$, even after a
constant fraction of the coordinates have been corrupted.
Yekhanin (2008)
constructed a $3$-query LDC ... more >>>

TR14-094 | 24th July 2014
Zeev Dvir, Sivakanth Gopi

2-Server PIR with sub-polynomial communication

A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the $i$th bit of an $n$-bit database replicated among two servers (which do not communicate) while not revealing any information about $i$ to either server. In this work we construct a 1-round 2-server PIR with total communication cost ... more >>>

TR15-086 | 28th May 2015
Jop Briet

On Embeddings of $\ell_1^k$ from Locally Decodable Codes

We show that any $q$-query locally decodable code (LDC) gives a copy of $\ell_1^k$ with small distortion in the Banach space of $q$-linear forms on $\ell_{p_1}^N\times\cdots\times\ell_{p_q}^N$, provided $1/p_1 + \cdots + 1/p_q \leq 1$ and where $k$, $N$, and the distortion are simple functions of the code parameters. We exhibit ... more >>>

ISSN 1433-8092 | Imprint