Computational Code-Based Single-Server Private Information Retrieval

Lukas Holzbaur, Camilla Hollanti, Antonia Wachter-Zeh

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

Abstract

A new computational private information retrieval (PIR) scheme based on random linear codes is presented. A matrix of messages from a McEliece scheme is used to query the server with carefully chosen errors. The server responds with the sum of the scalar multiple of the rows of the query matrix and the files. The user recovers the desired file by erasure decoding the response. Contrary to code-based cryptographic systems, the scheme presented here enables to use truly random codes, not only codes disguised as such. Further, we show the relation to the so-called error subspace search problem and quotient error search problem, which we assume to be difficult, and show that the scheme is secure against attacks based on solving these problems.

Original languageEnglish
Title of host publication2020 IEEE International Symposium on Information Theory, ISIT 2020 - Proceedings
PublisherIEEE
Pages1065-1070
Number of pages6
ISBN (Electronic)9781728164328
DOIs
Publication statusPublished - Jun 2020
MoE publication typeA4 Article in a conference publication
EventIEEE International Symposium on Information Theory - Los Angeles, United States
Duration: 21 Jul 202026 Jul 2020

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
PublisherIEEE
Volume2020-June
ISSN (Print)2157-8095

Conference

ConferenceIEEE International Symposium on Information Theory
Abbreviated titleISIT
CountryUnited States
CityLos Angeles
Period21/07/202026/07/2020

Fingerprint Dive into the research topics of 'Computational Code-Based Single-Server Private Information Retrieval'. Together they form a unique fingerprint.

Cite this