Improved user-private information retrieval via finite geometry

Oliver Gnilke, Marcus Greferath, Camilla Hollanti, Guillermo Nunez, Padraig Ó Catháin, Eric Swartz

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)
148 Downloads (Pure)


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.
Original languageEnglish
Pages (from-to)665–677
Number of pages13
Issue number2-3
Early online date21 Dec 2018
Publication statusPublished - Mar 2019
MoE publication typeA1 Journal article-refereed


  • Privacy
  • Communication
  • Finite geometry


Dive into the research topics of 'Improved user-private information retrieval via finite geometry'. Together they form a unique fingerprint.

Cite this