Symmetric Private Information Retrieval with Mismatched Coded Messages and Randomness
Symmetric Private Information Retrieval with Mismatched Coded Messages and Randomness
复制标题
DOI：
10.1109/isit.2019.8849351
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Qiwen Wang;Hua Sun;M. Skoglund
中科院分区：
文献类型：
--
作者：
Qiwen Wang;Hua Sun;M. Skoglund
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_{{\text{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_{{\text{mis}} - {\text{MDS}} - {\text{SPIR}}}} = \left( {1 - \frac{1}{N}} \right) \cdot {\left( {1 + \frac{{M - 1}}{N}\left( {1 + \frac{M}{N} + \cdots + {{\left( {\frac{M}{N}} \right)}^{K - 2}}} \right)} \right)^{ - 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.
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_{{\text{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_{{\text{mis}} - {\text{MDS}} - {\text{SPIR}}}} = \left( {1 - \frac{1}{N}} \right) \cdot {\left( {1 + \frac{{M - 1}}{N}\left( {1 + \frac{M}{N} + \cdots + {{\left( {\frac{M}{N}} \right)}^{K - 2}}} \right)} \right)^{ - 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.