Technical Program

Paper Detail

Paper IDP.9.5
Paper Title Computational Code-Based Single-Server Private Information Retrieval
Authors Lukas Holzbaur, Technical University of Munich, Germany; Camilla Hollanti, Aalto University, Finland; Antonia Wachter-Zeh, Technical University of Munich, Germany
Session P.9: Private Information Retrieval II
Presentation Lecture
Track Cryptography, Security and Privacy
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
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.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!