Private information retrieval

Private Information Retrieval ( PIR ) is a cryptographic primitive that models a protocol in which a request can be made to a database and answered without the database being able to make statements about the requested entry. The inquiries cannot therefore be linked to one another in order to determine the interests of the inquirer. In this way the privacy of the inquirer is supported, even if he is using public databases.

Modeling

Often the scheme is modeled as follows:

A database consisting of bits, e.g. B. ${\ displaystyle A}$ ${\ displaystyle n \ times n}$ ${\ displaystyle A \ in \ mathbb {B} ^ {n \ times n}}$
A client that queries a database entry - i.e. a column and row index - and receives a bit back

After execution, the following conditions must apply:

The client received the correct bit so that applies ${\ displaystyle b \ in A}$ ${\ displaystyle b = (A_ {ij})}$
The requested row and column index remained unknown to the database.

implementation

The easiest way to implement this scenario would be that the database - regardless of the query - always sends the entire content of the matrix as a response. Since this is difficult or impossible to implement with large amounts of data, there are other approaches, such as B. a solution by means of the quadratic residues problem.

literature

E, Kushilevitz and R. Ostrovsky: Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval . In: FOCS '97 . 1997 ( online ).
B. Chor, O Goldreich, E. Kushilevitz and M Sudan: Private Information Retrieval . Vol. 45. In: Journal of the ACM . No. 6 , November 1998, pp. 965-982 ( cs.umd.edu [PDF]).
Felipe Saint-Jean: A Java Implementation of a Single-Database Computationally Symmetric Private Information Retrieval (cSPIR) protocol . In: Yale University Technical Report YALEU / DCS / TR-1333 . YALEU / DCS / TR-1333, July 2005 ( stanford.edu [PDF]).

Individual evidence

↑ Fraunhofer FOKUS Competence Center Public IT: The ÖFIT trend sonar in IT security - Private Information Retrieval. April 2016, accessed May 26, 2016 .
↑ See also cs.ucla.edu

[1] Fraunhofer FOKUS Competence Center Public IT: The ÖFIT trend sonar in IT security - Private Information Retrieval. April 2016, accessed May 26, 2016 .

[2] See also cs.ucla.edu