Få dold information
Privat informationssökning ( PIR )
I kryptografi tillåter Information Retrieval Protocol (PIR) en konsument (eller spelare) att hämta privat information av intresse från en server. Dessutom kommer servern inte att kunna känna igen vilken del av dess information som har blivit känd för spelaren. Uppgift: Det finns en databas som består av bitar. Det finns en spelare som vill få ett bitnummer så att databasen som innehåller alla bitarna inte kan få reda på någon information om vilken bit spelaren fick. En trivial (men inte effektiv) lösning är att skicka alla bitar till spelaren, inklusive -biten han letar efter. Ett annat sätt är att använda PIR-protokollet där spelaren ställer en fråga (funktion) till databasen. Den senare tar denna funktion, tillämpar den på hela databassamlingen och får ett svar som skickas tillbaka till spelaren. Villkoren för detta spel är följande:
1) Längden på summan av frågan (funktionen) och svaret måste vara mycket mindre än n.
2) spelaren måste skicka en sådan fråga till vem som helst så att svaret är korrekt, det vill säga -biten togs emot korrekt.
3) Databasen kan inte lära sig något om .
Problemformuleringen för flera kopior av en databas formulerades först av Shore, Goldreich, Kushelevitz och Sudan 1996. Författarna föreslog en lösning [1] som krävde flera kopior av databasen -- och att servrarna som innehöll dessa kopior inte var tillåtna att kommunicera med varandra.
För första gången gavs lösningen av samma problem för en server och en spelare av Eyal Kushelevits och Rafail Ostrovsky 1997. De visade [2] att längden på fråge- och svarsumman är lika för alla . Dessa arbeten gav impulser till den intensiva utvecklingen av denna del av privat informationsinhämtning .
