Cryptanalysis of a Fast Private Information Retrieval Protocol

Jiayang Liu, Jingguo Bi

Published May 24, 2016• 4 citations

Abstract

A private information retrieval (abbreviated as PIR) protocol deals with the schemes that allow a user to retrieve privately an element of a non-replicated database. The security of PIR protocol is that the user wants to retrieve information in a database without the database knowing which information has being retrieved. This is widely applied in medical files, video or songs databases or even stock exchanges share prices.

DOI: 10.1145/2898420.2898427

Related papers

An Efficient Scheme for Private Information Retrieval

Weiwei Jing

The Private Information Retrieval protocol(PIR) is an important secure multi-party computation protocol.In PIR,a user can perform a query from a database without revealing his private information;meanwhile the privacy of the database will be protected,too.This paper proposes a new scheme in which we apply cryptographic technology on the auxiliary random servers protocol to solve the problem of PIR.This scheme is efficient in computational complexity and doesn't increase the cost of communication.It is very practical and can retrieve a block of bits.Detailed analysis of security,computational complexity and communicational complexity to the scheme is also given in this paper.

Journal of Chinese Computer SystemsJan 1, 20070 citations

Storage Constrained Information Theoretic Symmetric Private Information Retrieval

Deepak Kumar

Private information retrieval (PIR) is an important protocol in cryptographic community to ensure privacy of the user when retrieving information from untrusted databases. In a variation to this problem, symmetric private information retrieval (SPIR) is a protocol which ensures the privacy of user as well as databases. A major drawback for the majority of existing works on information theoretic PIR and SPIR is that they focus on scenarios where all databases store the entire data set (i.e. replicated databases). The goal of this thesis is to present PIR and SPIR schemes for storage constrained databases. For both PIR and SPIR, we present a systematic approach to utilize storage constrained databases. The technical contribution involves two main parts: (a) a careful storage scheme to split and store messages across databases; and (b) construction of information theoretic PIR and SPIR schemes from such databases. We also compare our results to the fully replicated scenario, as well as compare the differences between the communication overhead of PIR and SPIR schemes.

Jun 25, 20180 citations

The Capacity of Symmetric Private Information Retrieval

Hua Sun, Syed A. Jafar

Private information retrieval (PIR) is the problem of retrieving as efficiently as possible, one out of K messages from N non-communicating replicated databases (each holds all K messages) while keeping the identity of the desired message index a secret from each individual database. Symmetric PIR (SPIR) is a generalization of PIR to include the requirement that beyond the desired message, the user learns nothing about the other K - 1 messages. The information theoretic capacity of SPIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. We show that the capacity of SPIR is 1-1/N regardless of the number of messages K, if the databases have access to common randomness (not available to the user) that is independent of the messages, in the amount that is at least 1/(N -1) bits per desired message bit, and zero otherwise.

IEEE Globecom Workshops (GC Wkshps)Dec 1, 201651 citations

Σ-private private information retrieval protocols

Zhang Zi

We pose the definition ofΣ-private private information retrieval(PIR)protocol,and then construct a Σ-private PIR protocol based on verifiable secret sharing(VSS)scheme on general access structure.We also construct an efficient robustΣ-private PIR protocol based on robust multiplication protocol and the database is also secure.The corresponding communication complexity is dependent on the size of the access structure and is efficient for minority of servers.

Journal of the Graduate School of the Chinese Academy of SciencesJan 1, 20110 citations

Almost Optimal Private Information Retrieval

Dmitri Asonov, Freytag, J.C., Humboldt-Universitaet, Berlin (Germany). Inst. fuer Informatik

A private information retrieval (PIR) protocol allows a user to retrieve one of N records from a database while hiding the identity of the record from the database server.

Jan 1, 200111 citations

The Capacity of Symmetric Private Information Retrieval

Hua Sun, Syed A. Jafar

Private information retrieval (PIR) is the problem of retrieving, as efficiently as possible, one out of K messages from N non-communicating replicated databases (each holds all K messages) while keeping the identity of the desired message index a secret from each individual database. Symmetric PIR (SPIR) is a generalization of PIR to include the requirement that beyond the desired message, the user learns nothing about the other K - 1 messages. The information theoretic capacity of SPIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. We show that the capacity of SPIR is 1-1/N regardless of the number of messages K, if the databases have access to common randomness (not available to the user) that is independent of the messages, in the amount that is at least 1/(N -1) bits per desired message bit. Otherwise, if the amount of common randomness is less than 1/(N -1) bits per message bit, then the capacity of SPIR is zero. Extensions to the capacity region of SPIR and the capacity of finite length SPIR are provided.

IEEE Transactions on Information TheoryJun 19, 2018187 citations