Improved user-private information retrieval via finite geometry

Research output: Contribution to journalArticleScientificpeer-review

Researchers

Research units

  • Worcester Polytechnic Institute
  • College of William and Mary
  • Technical University of Munich

Abstract

In a user-private information retrieval (UPIR) scheme, a set of users collaborate to retrieve files from a database without revealing to observers which participant in the scheme requested the file. To achieve privacy, users retrieve files from the database in response to anonymous requests posted to message spaces; assuming that each message space can be accessed by a subset of the participants in the scheme. Privacy with respect to the database is easily achieved, but privacy with respect to coalitions of other users within the scheme is sensitive to the choice of incidence structure determining which users can access each message space. Earlier schemes were based on pairwise balanced designs and symmetric designs, and involved at most one step of message passing to retrieve a file. We propose a new class of UPIR schemes based on generalised quadrangles (GQs), which need up to two steps of message passing in each file retrieval. We introduce a new message passing protocol in which messages are encrypted. Even using this protocol, previously proposed schemes are compromised by finite coalitions of users. We construct a family of GQ-UPIR schemes which maintain privacy with high probability even when O(n1/2−ϵ) users collude, where n is the total number of users in the scheme. We also show that a UPIR scheme based on any family of generalised quadrangles is secure against coalitions of O(n1/4−ϵ) users.

Details

Original languageEnglish
Pages (from-to)665–677
Number of pages13
JournalDESIGNS CODES AND CRYPTOGRAPHY
Volume87
Issue number2-3
Early online date21 Dec 2018
Publication statusPublished - Mar 2019
MoE publication typeA1 Journal article-refereed

    Research areas

  • Privacy, Communication, Finite geometry

Download statistics

No data available

ID: 30549236