I problemet med privat informationshämtning (PIR) vill en användare, så effektivt som möjligt, hämta ett av K-meddelanden från icke-kommunikationsdatabaser (var och en innehåller alla K-meddelanden) utan att avslöja något om identiteten på det önskade meddelandeindexet till någon enskild databas. Den teoretiska kapaciteten hos PIR är det maximala antalet bitar av önskad information som kan hämtas privat per bit nedladdad information. För K-meddelanden och N-databaser visar vi att PIR-kapaciteten är 1 + 1/N + 1/N 2 + · · · + 1/N K‐1 −1. Ett anmärkningsvärt drag i systemet för kapacitetsuppnående är att om vi eliminerar någon delmängd av meddelanden (genom att sätta meddelandesymbolerna till noll), uppnår det resulterande systemet också PIR-kapaciteten för den återstående delmängd av meddelanden.
Genom att utnyttja fördelarna med replikering av databasen i icke-colluding servrar, privat informationshämtning kan uppnås utan att ladda ner alla meddelanden och kapaciteten för detta problem kännetecknas i REF.
The Capacity of Private Information Retrieval
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}