Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/47992
Title: A study of private information retrieval and related primitives.
Authors: Zhang, Liang Feng
Keywords: DRNTU::Science::Mathematics::Discrete mathematics::Cryptography
Issue Date: 2011
Source: Zhang, L. F. (2011). A study of private information retrieval and related primitives. Doctoral thesis, Nanyang Technological University, Singapore.
Abstract: 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.
URI: https://hdl.handle.net/10356/47992
DOI: 10.32657/10356/47992
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Theses

Files in This Item:
File Description SizeFormat 
spmsG0701014G.pdfMain article681.92 kBAdobe PDFThumbnail
View/Open

Page view(s)

336
checked on Oct 26, 2020

Download(s)

150
checked on Oct 26, 2020

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.