Indhentning af skjult information
Privat informationssøgning ( PIR )
I kryptografi giver Information Retrieval Protocol (PIR) en forbruger (eller spiller) mulighed for at hente private oplysninger af interesse fra en server. Desuden vil serveren ikke være i stand til at genkende, hvilken del af dens information, der er blevet kendt af spilleren. Opgave: Der er en database bestående af bits. Der er en spiller, der ønsker at få et bitnummer , så databasen med alle bits ikke kan finde ud af nogen information om, hvilken bit spilleren fik. En triviel (men ikke effektiv) løsning er at sende alle bits til spilleren, inklusive den -bit han leder efter. En anden måde er at bruge PIR-protokollen, hvor spilleren stiller et spørgsmål (funktion) til databasen. Sidstnævnte tager denne funktion, anvender den på hele databasesamlingen og modtager et svar, der sendes tilbage til afspilleren. Betingelserne for dette spil er som følger:
1) Længden af summen af spørgsmålet (funktionen) og svaret skal være meget mindre end n.
2) spilleren skal sende et sådant spørgsmål til enhver, så svaret er korrekt, det vil sige -bitten blev korrekt modtaget.
3) Databasen kan ikke lære noget om .
Problemformuleringen for flere kopier af en database blev først formuleret af Shore, Goldreich, Kushelevitz og Sudan i 1996. Forfatterne foreslog en løsning [1] , der krævede flere kopier af databasen -- og at serverne med disse kopier ikke var tilladte at kommunikere med hinanden.
For første gang blev løsningen af det samme problem for én server og én spiller givet af Eyal Kushelevits og Rafail Ostrovsky i 1997. De viste [2] at længden af spørgsmålet og svarsummen er lig for enhver . Disse værker satte skub i den intensive udvikling af denne del af privat informationssøgning .
