Technical Program

Paper Detail

Paper IDP.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

Visit Website!