Paper Title |
Symmetric Private Information Retrieval with Mismatched Coded Messages and Randomness |

Paper Identifier | MO3.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. |