Private Information Retrieval from Colluding and Byzantine Servers with Binary Reed-Muller Codes

Perttu Saarela, Matteo Allaix, Ragnar Freij-Hollanti, Camilla Hollanti

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

2 Citations (Scopus)

Abstract

This paper is eligible for the Jack Keil Wolf ISIT Student Paper Award. In this work, a flexible and robust private information retrieval (PIR) scheme based on binary non-maximum distance separable (non-MDS) codes is considered. This combines previous works on PIR schemes based on transitive non-MDS codes on one hand, and PIR from MDS-coded Byzantine and nonresponsive servers on the other hand. More specifically, a PIR scheme employing binary Reed-Muller (RM) codes tolerant to colluding, Byzantine, and non-responsive servers is constructed, and bounds for the achievable rates are derived under certain conditions. The construction of such schemes turns out to be much more involved than for MDS codes. Namely, the binary query vectors have to be selected with great care to hit the desired information sets, which is technically challenging as will be shown.

Original languageEnglish
Title of host publication2022 IEEE International Symposium on Information Theory, ISIT 2022
PublisherIEEE
Pages2839-2844
Number of pages6
ISBN (Electronic)978-1-6654-2159-1
DOIs
Publication statusPublished - 2022
MoE publication typeA4 Conference publication
EventIEEE International Symposium on Information Theory - Espoo, Finland
Duration: 26 Jun 20221 Jul 2022

Publication series

NameIEEE International Symposium on Information Theory
ISSN (Electronic)2157-8117

Conference

ConferenceIEEE International Symposium on Information Theory
Abbreviated titleISIT
Country/TerritoryFinland
CityEspoo
Period26/06/202201/07/2022

Fingerprint

Dive into the research topics of 'Private Information Retrieval from Colluding and Byzantine Servers with Binary Reed-Muller Codes'. Together they form a unique fingerprint.

Cite this