Private Information Retrieval Protocols Based on Transversal Designs
Translated title
Transversal Design Baserede Private Information Retrieval Protokoller
Author
Martinsen, Christian Juel
Term
4. term
Education
Publication year
2021
Submitted on
2021-06-04
Pages
46
Abstract
This thesis explores private information retrieval (PIR), which allows a user to fetch an item from several servers without revealing which item it is. We present constructions of 1-private and (t−1)-private PIR protocols, explain how they work, and discuss their properties. Our approach builds PIR from transversal designs—balanced combinatorial layouts—constructed using orthogonal arrays and generalized Reed–Solomon (GRS) codes, a class of error-correcting codes. This combination leads to effective PIR protocols, but we identify and explain a constraint on the permissible size of the GRS code in this setting. We also compare these methods to a general PIR scheme for coded storage with colluding servers, where coded storage spreads data across servers using codes. That scheme achieves a high information rate (a large amount of useful data per unit of download) and favorable storage efficiency, while the transversal-design-based PIR has very low computational complexity.
Denne afhandling undersøger private information retrieval (PIR), som gør det muligt for en bruger at hente en post fra flere servere uden at afsløre, hvilken post det er. Vi præsenterer konstruktioner af 1-privat og (t−1)-privat PIR-protokoller, forklarer hvordan de virker og gennemgår deres egenskaber. Tilgangen bygger PIR på transversale designs—balancerede kombinatoriske opstillinger—konstrueret ved hjælp af ortogonale arrays og generaliserede Reed–Solomon (GRS)-koder, en klasse af fejlkorrigerende koder. Denne kombination giver gode PIR-protokoller, men vi påviser og forklarer en begrænsning på den tilladte størrelse af GRS-koden i denne sammenhæng. Vi sammenligner også med et generelt PIR-skema for kodet lagring med samarbejdende servere, hvor kodet lagring spreder data over servere ved hjælp af koder. Dette skema opnår høj informationsrate (meget nyttig data i forhold til den downloadede datamængde) og gode lagringsegenskaber, mens den transversale design-baserede PIR-tilgang har meget lav beregningsmæssig kompleksitet.
[This apstract has been rewritten with the help of AI based on the project's original abstract]
Keywords