Necessary and Sufficient Conditions for Capacity-Achieving Private Information Retrieval with Non-Colluding and Colluding Servers

Atsushi Miki, Yusuke Morishita, Toshiyasu Matsushima

Private Information Retrieval (PIR) is a mechanism for efficiently downloading messages while keeping the index secret. Here, PIRs in which servers do not communicate with each oth…