The Minimum Upload Cost of Symmetric Private Information Retrieval
Yanliang Zhou, Qiwen Wang, Hua Sun, Shengli Fu · 2020
For the symmetric private information retrieval problem with K messages and N servers, we show that the minimum (symmetric) upload cost is log2(⌈K1/N-1⌉) bits per server, i.e., the user must upload a q-ary symbol to each server where q is at least ⌈K1/N-1⌉.