Symmetric Private Information Retrieval with Mismatched Coded Messages and Randomness
Qiwen Wang, Hua Sun, Mikael Skoglund · 2019
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 CMDS-SPIR= 1- 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 Cmis-MDS-SPIR= (1 - 1/N) · (1+M-1/N (1 + M/N + ⋯ + (M/N)K-2))-1. Interestingly, Cmis-MDS-SPIR> CMDS-SPIR, so mismatched coded randomness (with more redundancy) is strictly beneficial. Further, mismatched SPIR exhibits properties that are similar to PIR.