2023/01/05 by Chao Tian, Tian, Chao, Sun Hua +3
Computer Science · #Algorithms and Data Compression #Chaos-based Image/Signal Encryption #Cryptography and Data Security #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2301.02155
openalex publication_date 2023/01/05 · openalex created_date 2023/01/08 · openalex updated_date 2026/07/28
We consider the storage-retrieval rate tradeoff in private information retrieval (PIR) systems using a Shannon-theoretic approach. Our focus is mostly on the canonical two-message two-database case, for which a coding scheme based on random codebook generation and the binning technique is proposed. This coding scheme reveals a hidden connection between PIR and the classic multiple description source coding problem. We first show that when the retrieval rate is kept optimal, the proposed non-linear scheme can achieve better performance over any linear scheme. Moreover, a non-trivial storage-retrieval rate tradeoff can be achieved beyond space-sharing between this extreme point and the other optimal extreme point, achieved by the retrieve-everything strategy. We further show that with a method akin to the expurgation technique, one can extract a zero-error PIR code from the random code. Outer bounds are also studied and compared to establish the superiority of the non-linear codes over linear codes.