Symmetric Private Information Retrieval with Mismatched Coded Messages and Randomness

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.