Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PRIVATE INFORMATION RETRIEVAL:
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

We show that any 1-round 2-server Private Information
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