Skip to main content


Weitere Artikel dieser Ausgabe durch Wischen aufrufen

21.12.2018 | Ausgabe 2-3/2019 Open Access

Designs, Codes and Cryptography 2-3/2019

Improved user-private information retrieval via finite geometry

Designs, Codes and Cryptography > Ausgabe 2-3/2019
Oliver W. Gnilke, Marcus Greferath, Camilla Hollanti, Guillermo Nuñez Ponasso, Padraig Ó Catháin, Eric Swartz
Wichtige Hinweise
This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Coding and Cryptography”.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.


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(n^{1/2-\epsilon })\) 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(n^{1/4-\epsilon })\) users.
Über diesen Artikel

Weitere Artikel der Ausgabe 2-3/2019

Designs, Codes and Cryptography 2-3/2019 Zur Ausgabe

Premium Partner