Private information retrieval protocols guarantee that a user can privately and losslessly retrieve a single file from a database stored across multiple servers. In this work, we propose to simultaneously relax the conditions of perfect retrievability and privacy in order to obtain improved download rates when all files are stored uncoded on a single server. Information leakage is measured in terms of the average success probability for the server of correctly guessing the identity of the desired file. The main findings are: i) The derivation of the optimal tradeoff between download rate, distortion, and information leakage when the file size is infinite. Closed-form expressions of the optimal tradeoff for the special cases of "no-leakage" and "no-privacy" are also given. ii) A novel approach based on linear programming (LP) to construct schemes for a finite file size and an arbitrary number of files. The proposed LP approach can be leveraged to find provably optimal schemes with corresponding closed-form expressions for the rate-distortion-leakage tradeoff when the database contains at most four bits. Finally, for a database that contains 320 bits, we compare two construction methods based on the LP approach with a nonconstructive scheme downloading subsets of files using a finite-length lossy compressor based on random coding.
翻译:私自信息检索协议保证用户可以私下和无损地从多个服务器存储的数据库中检索单个文件。 在这项工作中,我们建议同时放宽完全可检索性和隐私的条件,以便在所有文件都存储在单一服务器上而不编码的情况下获得更好的下载率。信息泄漏的衡量依据是正确猜测所需文件身份的服务器的平均成功概率。主要结论是:(i) 当文件大小无限时,在下载率、扭曲和信息渗漏之间得出最佳的取舍。对于“无泄漏”和“无隐私”等特殊案例,我们建议同时放宽完全可检索和隐私的条件,以便在所有文件被存储在单一服务器上时获得更好的下载率。基于线性编程的编程(LP),以构建一个限定文件大小和任意文件数量的计划的新办法。可以利用拟议的LP 方法,在数据库最多包含四个位时,找到具有相应超缩放式表达式的下载率、扭曲和信息渗漏交易的最佳取法。最后,对于包含320位位位元和“无隐私”的特写式,我们用一种基于LP 软质版本的固定版本的版本文件系统模式来比较两种构建方法。