Amos Beimel, Yuval Ishai

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

Iordanis Kerenidis, Ronald de Wolf

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

Richard Beigel, Lance Fortnow, William Gasarch

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

David P. Woodruff, Sergey Yekhanin

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

Alexander Razborov, Sergey Yekhanin

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

Sergey Yekhanin

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

Rafail Ostrovsky, William Skeith

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

Klim Efremenko

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

Yeow Meng Chee, Tao Feng, San Ling, Huaxiong Wang, Liang Feng Zhang

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

Zeev Dvir, Sivakanth Gopi

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

Jop Briet

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