A study of private information retrieval and related primitives.
In this thesis, we study four notions related to Private Information Retrieval (PIR), namely Extended Private Information Retrieval (EPIR), Locally Decodable Codes (LDCs), Distributed Oblivious Transfer (DOT) and Oblivious Linear Function Evaluation (OLFE). EPIR allows a user to evaluate a fu...
Saved in:
Main Author: | |
---|---|
Other Authors: | |
Format: | Theses and Dissertations |
Language: | English |
Published: |
2012
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/47992 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
Summary: | In this thesis, we study four notions related to Private Information Retrieval (PIR), namely
Extended Private Information Retrieval (EPIR), Locally Decodable Codes (LDCs),
Distributed Oblivious Transfer (DOT) and Oblivious Linear Function Evaluation (OLFE).
EPIR allows a user to evaluate a function on one of the data blocks of a server,
in such a way that the server learns no information on neither the function nor the identity of the accessed
data block, and the user cannot learn more
information on the data blocks except the evaluation.
Bringer and Chabanne (2009) proposed an EPIR protocol where
the user's function is a polynomial over a finite field and the server's data blocks are
elements of the field. In Chapter \ref{chap:EPIR}, we show that their protocol fails
frequently when one coefficient of the user's polynomial
is primitive in the finite field and the others belong to the prime subfield of the field. Our results call for new EPIR protocols that avoid the above deficiency.
LDCs allow one to encode
a message as a codeword such that each symbol of the message can be recovered by a probabilistic
decoding algorithm which only looks at a small number of coordinates of the codeword,
even if a constant fraction of the codeword has been corrupted.
Efremenko (2009) proposed a framework for constructing constant-query LDCs of subexponential length.
Within this framework, LDCs of query complexity as small as 3 can be obtained.
These codes depend on composite numbers which have nice algebraic properties.
In Chapter \ref{chap:LDC}, we present our discovery of a new class of algebraically nice
numbers. In particular, we show that {\em Mersenne numbers}
(numbers of the form $M_t=2^t-1$, where $t$ is a prime) which are products of two primes are algebraically nice.
These numbers enable us to improve the known constructions of LDCs and PIR protocols.
DOTs are oblivious transfers in the distributed setting where the receiver can learn a secret of the sender with
the help of intermediate servers. Compared with the classical oblivious transfers, DOTs are
computationally efficient and achieve information-theoretic privacy.
However, the known DOT protocols have linear communication complexity between the receiver and servers,
which
may be prohibitive when the sender has a huge number of secrets.
In Chapter \ref{chap:DOT}, we propose both a specific reduction from DOT to polynomial interpolation-based
PIR and a general reduction from DOT to any PIR. Our reductions yield the first
DOT protocols of sublinear communication complexity between the receiver and servers.
OLFE is
a cryptographic primitive between two parties where one party has
a multivariate
linear function and the other party wants to evaluate the function on a private input.
In Chapter \ref{chap:OLFE}, we introduce this primitive and present its interesting applications in the
cryptographic study and protocol design.
We give an unconditionally secure
and fully simulatable reduction from
classical OT to OLFE. Specifically, we show that
any classical OT can
be unconditionally securely reduced
to a number of invocations of
a given OLFE except for a negligible
failure probability. Using this reduction, we show that
any classical OT can be efficiently reversed in the sense that the roles of the sender and the receiver
are interchanged. |
---|