2021/11/09 by Yauhen Yakimenka, Hsuan-Yin Lin, Yakimenka, Yauhen +5
Computer Science · #Cryptography and Data Security #FOS: Computer and information sciences #Information Theory (cs.IT) #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2111.05160
openalex publication_date 2021/11/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Private information retrieval protocols guarantee that a user can privately\nand losslessly retrieve a single file from a database stored across multiple\nservers. In this work, we propose to simultaneously relax the conditions of\nperfect retrievability and privacy in order to obtain improved download rates\nwhen all files are stored uncoded on a single server. Information leakage is\nmeasured in terms of the average success probability for the server of\ncorrectly guessing the identity of the desired file. The main findings are: i)\nThe derivation of the optimal tradeoff between download rate, distortion, and\ninformation leakage when the file size is infinite. Closed-form expressions of\nthe optimal tradeoff for the special cases of "no-leakage" and "no-privacy" are\nalso given. ii) A novel approach based on linear programming (LP) to construct\nschemes for a finite file size and an arbitrary number of files. The proposed\nLP approach can be leveraged to find provably optimal schemes with\ncorresponding closed-form expressions for the rate-distortion-leakage tradeoff\nwhen the database contains at most four bits.\n Finally, for a database that contains 320 bits, we compare two construction\nmethods based on the LP approach with a nonconstructive scheme downloading\nsubsets of files using a finite-length lossy compressor based on random coding.\n