A Novel Perfect Privacy Preserving Single Database Private Information Retrieval with Non-trivial Communication

Radhakrishna Bhat, N. R. Sunitha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Most of the existing user privacy preserving techniques rely on the existing intractability assumption based data privacy concepts that greatly reduces the chances of providing perfect privacy (i.e., no information about the user interest is revealed over the curious server) to the user. In order to fill this gap, we have presented a perfect privacy preserving single database scheme with non-trivial communication cost using the concept called Private Information Retrieval (PIR). We have suc-cessfully overcome the basic requirement of $\Omega(n)$ communication for any single database information-theoretic private information retrieval as claimed by Chor et.al [1] by breaking the dependency of both user privacy and data privacy on a single intractability assumption where n is the size of the database.In the proposed scheme, information-theoretic queries are generated by extending the query input domain to$\mathbb {Z-{N}^{+1}}$ (i.e., all queries can select their inputs from $\mathbb {Z-{N}^{+1}}$ with identically distributed probability) where N is the RSA composite modulus which is an improvement to the quadratic residuosity based user privacy preserving technique presented in [2] (Note that in [2], query may contain computationally indistinguishable input either from quadratic residue set or from quadratic non-residue set). We have presented a new recursive trapdoor bit based linking function which takes the information-theoretic query and the database and produces a non-trivial communication response. Additionally, we have extended the proposed scheme to a new scheme with reduced communication by using a new compression method.

Original languageEnglish
Title of host publication2017 2nd International Conference On Emerging Computation and Information Technologies, ICECIT 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Print)9781538610947
DOIs
Publication statusPublished - 31-08-2018
Event2nd International Conference On Emerging Computation and Information Technologies, ICECIT 2017 - Tumakuru, India
Duration: 15-12-201716-12-2017

Publication series

Name2017 2nd International Conference On Emerging Computation and Information Technologies, ICECIT 2017

Conference

Conference2nd International Conference On Emerging Computation and Information Technologies, ICECIT 2017
Country/TerritoryIndia
CityTumakuru
Period15-12-1716-12-17

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Computer Vision and Pattern Recognition
  • Information Systems
  • Safety, Risk, Reliability and Quality

Fingerprint

Dive into the research topics of 'A Novel Perfect Privacy Preserving Single Database Private Information Retrieval with Non-trivial Communication'. Together they form a unique fingerprint.

Cite this