2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | P.8.4 | ||
| Paper Title | The Minimum Upload Cost of Symmetric Private Information Retrieval | ||
| Authors | Yanliang Zhou, University of North Texas, United States; Qiwen Wang, Huawei, Sweden; Hua Sun, Shengli Fu, University of North Texas, United States | ||
| Session | P.8: Private Information Retrieval I | ||
| Presentation | Lecture | ||
| Track | Cryptography, Security and Privacy | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | For the symmetric private information retrieval problem with $K$ messages and $N$ servers, we show that the minimum (symmetric) upload cost is $\log_2 \left( \lceil {K}^{\frac{1}{N-1}} \rceil \right)$ bits per server, i.e., the user must upload a $q$-ary symbol to each server where $q$ is at least $\lceil {K}^{\frac{1}{N-1}} \rceil$. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
