Vi studerar Privat Information Retrieval med Sidoinformation (PIR-SI) i en-server multi-meddelande inställning. I den här inställningen vill en användare ladda ner D-meddelanden från en databas med K ≥ D-meddelanden som lagras på en enda server, utan att avslöja någon information om identiteterna på de begärda meddelandena till servern. Målet för användaren är att uppnå informationsteoretisk integritet genom att utnyttja sidoinformationen om databasen. Sidoinformationen består av en slumpmässig delmängd av M-meddelanden. Namnen på de meddelanden som bildar sidoinformationen är till en början okända för servern. Vårt mål är att karakterisera kapaciteten i denna inställning, dvs. den maximala möjliga nedladdningshastigheten. I vårt tidigare arbete har vi etablerat PIR-SI-kapaciteten för specialfall där användaren vill ha ett enda meddelande, d.v.s. D = 1 och visat att kapaciteten kan uppnås genom delnings- och kodsystemet. I det här dokumentet fokuserar vi på fallet när användaren vill ha flera meddelanden, d.v.s., D > 1. Vårt första resultat är att om användaren vill ha fler meddelanden än vad de har som sidoinformation, dvs D > M, då kapaciteten är D K‐M, och det kan uppnås med hjälp av ett system baserat på Generalized Reed-Solomon koder. Vårt andra resultat visar att när D ≤ M kan kapaciteten vara högre. Vi presenterar en lägre gräns på kapaciteten baserat på ett achievability system som vi kallar Generalized Partition and Code.
Den enda-server multi-message PIR med sidoinformationsproblem studeras samtidigt i REF, som har samma resultat som oss när N > M och presenterar achievability resultat när N ≤ M 1.
On the Capacity of Single-Server Multi-Message Private Information Retrieval with Side Information
{'venue': '2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton)', 'journal': '2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}