Technical Program

Paper Detail

Paper Title Symmetric Private Information Retrieval with Mismatched Coded Messages and Randomness
Paper IdentifierMO3.R3.4
Authors Qiwen Wang, KTH Royal Institute of Technology, Sweden; Hua Sun, University of North Texas, United States; Mikael Skoglund, KTH Royal Institute of Technology, Sweden
Session Private Information Retrieval I
Location Monge, Level 3
Session Time Monday, 08 July, 14:30 - 16:10
Presentation Time Monday, 08 July, 15:30 - 15:50
Manuscript  Click here to download the manuscript
Abstract The capacity of symmetric private information retrieval (PIR) with $N$ servers and $K$ messages, each coded by an $(N,M)$-MDS code has been characterized as $C_{\mathrm{MDS-SPIR}} = 1 - \frac{M}{N}$. A critical assumption for this result is that the randomness is similarly coded by an $(N,M)$-MDS code, i.e., the code parameters of the messages and randomness are matched. In this work, we are interested in the mismatched case, and as a preliminary result, we establish the capacity of the mismatched MDS coded symmetric PIR (SPIR) problem under an extreme setting, where the messages are coded by an $(N,M)$-MDS code and the randomness is replicated (i.e., coded by an $(N,1)$-MDS code). The capacity is shown to be $C_{\mathrm{mis-MDS-SPIR}} = (1 - \frac{1}{N}) \cdot \left( 1 + \frac{M-1}{N} (1 + \frac{M}{N} + \cdots + (\frac{M}{N})^{K-2}) \right)^{-1}$. Interestingly, $C_{\mathrm{mis-MDS-SPIR}} > C_{\mathrm{MDS-SPIR}}$, so mismatched coded randomness (with more redundancy) is strictly beneficial. Further, mismatched SPIR exhibits properties that are similar to PIR.