TH4.R9.4

Code-Based Single-Server Private Information Retrieval: Circumventing the Sub-Query Attack

Neehar Verma, Camilla Hollanti, Aalto University, School of Science, Finland

Session:
Private Information Retrieval 2

Track:
16: Private Information Retrieval

Location:
Lamda

Presentation Time:
Thu, 11 Jul, 17:25 - 17:45

Session Chair:
Viveck Cadambe, Pennsylvania State University
Abstract
Private information retrieval from a single server is considered, utilizing the hardness of the decoding problem of random linear codes. Presented is a modified version of the first code-based single-server computational PIR scheme proposed by Holzbaur, Hollanti, and Wachter-Zeh in [Holzbaur \emph{et al.}, ``Computational Code-Based Single-Server Private Information Retrieval'', \emph{2020 IEEE ISIT}]. The original scheme was broken in [Bordage \emph{et al.}, ``On the privacy of a code-based single-server computational PIR scheme'', \emph{Cryptogr. Comm.}, 2021] by an attack arising from highly probable rank differences in sub-matrices of the user's query. Here, this attack is now circumvented by ensuring that the sub-matrices have negligible rank difference. Furthermore, the rank difference cannot be attributed to the desired file index, thereby ensuring privacy. In the case of retrieving multiple files, the rate of the modified scheme is largely unaffected and at par with the original scheme.
Resources