Protokoll för privat informationshämtning (PIR) gör det möjligt för en användare att hämta ett dataobjekt från en databas utan att avslöja någon information om identiteten på det objekt som hämtas. Specifikt, i informationsteoretisk k- server PIR, databasen kopieras bland k icke- kommunikerande servrar, och varje server lär sig ingenting om objektet hämtas av användaren. Kostnaden för PIR-protokoll mäts vanligen i termer av deras kommunikationskomplexitet, vilket är det totala antalet bitar som utbyts mellan användaren och servrarna. En annan viktig kostnadsparameter är dock omkostnaderna för lagring, vilket är förhållandet mellan det totala antalet bitar som lagras på alla servrar och antalet bitar i databasen. Eftersom informations-teoretisk PIR för en enda server är omöjligt, är lagringen av alla befintliga PIR-protokoll minst 2 (eller k, när det gäller K-server PIR). I detta arbete visar vi att informationsteori PIR kan uppnås med lagring overhead godtyckligt nära det optimala värdet av 1, utan att offra kommunikationen komplexitet. Specifikt visar vi att alla kända K-server PIR protokoll effektivt kan emuleras, samtidigt som både integritet och kommunikation komplexitet men avsevärt minska lagring overhead. För detta ändamål distribuerar vi n bitar av databasen bland s + r servrar, varje lagring n / s kodade bitar (snarare än kopior). Framför allt förblir vårt kodningsprogram detsamma, oavsett om det specifika K-server-PIR-protokollet emuleras. För varje fast k, den resulterande lagring overhead (s + r) / s närmar sig 1 som s växer; explicit har vi r k 1 + o(1). Dessutom, i specialfallet k = 2, är förvaringen overhead endast 1 + 1 s. För att uppnå dessa resultat, vi introducerar och studera en ny typ av binär linjära koder, kallas här k-server PIR-koder. Vi visar sedan hur sådana koder kan konstrueras från Steiner system, från ett steg majoritetslogiska decodable koder, från konstant vikt koder, och från vissa lokalt återvinningskoder. Vi etablerar också flera gränser på parametrarna för K-server PIR-koder, och tabulerar resultaten för alla s 32 och k 16. Slutligen diskuterar vi kortfattat utvidgningar av våra resultat till icke-binära alfabet, till robust PIR och till t-privat PIR.
PIR-koder föreslogs i REF för att minska omkostnaderna för lagring i PIR-system som bevarar både integritet och kommunikations komplexitet.
PIR with Low Storage Overhead: Coding instead of Replication
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}