Private Information Retrieval
Author
Lex, Christian Jensen
Term
4. term
Education
Publication year
2021
Submitted on
2021-06-04
Pages
50
Abstract
This thesis introduces Private Information Retrieval (PIR), the task of fetching a specific item from servers without revealing which item is requested. Focusing on information-theoretic privacy—guarantees that do not rely on computational assumptions—it outlines core PIR ideas and compares the download efficiency (rate) of several promising schemes with known capacity-achieving limits. The work places these schemes in the setting of coded distributed storage, where data are encoded and spread across multiple servers, and explains how this impacts privacy and efficiency. A central tool is the use of Generalized Reed–Solomon (GRS) codes, a family of error-correcting codes with appealing properties for PIR. Because the presented schemes demand substantial server-side computation, the thesis proposes a variant that uses subfield subcodes of GRS codes (also known as alternant codes) to reduce the complexity of computing server responses. It also considers how a second scheme might be adapted using the same idea.
Denne specialeafhandling giver en introduktion til Private Information Retrieval (PIR), altså at hente et specifikt datapunkt fra servere uden at afsløre, hvilket datapunkt der efterspørges. Med fokus på informations-teoretisk privatliv—garantier der ikke afhænger af antagelser om beregningskraft—gennemgår afhandlingen de centrale idéer i PIR og sammenligner download-effektiviteten (raten) i flere lovende PIR-skemaer med kendte kapacitetsopnåelige grænser. Afhandlingen sætter skemaerne ind i sammenhængen af kodede distribuerede lagersystemer, hvor data kodes og fordeles på flere servere, og forklarer, hvordan dette påvirker privatliv og effektivitet. Et centralt værktøj er generaliserede Reed–Solomon (GRS) koder, en familie af fejlrettende koder med attraktive egenskaber i PIR-opsætninger. Da de præsenterede skemaer kræver betydelige beregninger på serversiden, præsenteres en variant, der bruger underfelts-underkoder af GRS-koder (også kaldet alternantkoder) for at reducere kompleksiteten i servernes beregning af svar. Der gives også overvejelser om en tilsvarende tilpasning af et andet skema.
[This apstract has been rewritten with the help of AI based on the project's original abstract]
Keywords