• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >The Capacity of Private Information Retrieval With Private Side Information Under Storage Constraints
【24h】

The Capacity of Private Information Retrieval With Private Side Information Under Storage Constraints

机译：存储限制下私人信息检索的能力

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We consider the problem of private information retrieval (PIR) of a single message out of K messages from N replicated and non-colluding databases where a cache-enabled user (retriever) of cache-size S possesses side information in the form of uncoded portions of the messages where the message identities are unknown to the databases. The identities of these side information messages need to be kept private from the databases, i.e., we consider PIR with private side information (PSI). We characterize the optimal normalized download cost for this PIR-PSI problem under the storage constraint S as D* = 1 + 1/N + i/N-2 + ... + 1/NK-1-M + 1-r(M)/NK-M + 1 - r(M-1)/N(K-1M+1)where M is the number of side information messages and ri is the portion of the ith side information message that is cached with Sigma(M)(i=1) r(i) = S. Based on this capacity result, we prove two facts: First, for a fixed memory size S and a fixed number of accessible messages M, uniform caching achieves the lowest normalized download cost, i.e., r(i) = S/M, for i = 1,..., M, is optimum. Second, for a fixed memory size S, among all possible K - [S] + 1 uniform caching schemes, the uniform caching scheme which caches M = K messages achieves the lowest normalized download cost.
机译：我们考虑私人信息检索（PIR）从来自N复制的和非勾结数据库的k消息中的单个消息的问题（PIR），其中高速缓存大小S的高速缓存的用户（检索器）以未编码的部分的形式拥有侧信息消息标识为数据库未知的消息。需要保密这些侧信息消息的标识，即，我们考虑具有私人侧信息（PSI）的PIR。我们在存储约束下表征了该PIR-PSI问题的最佳标准化下载成本为D * = 1 + 1 / n + I / N-2 + ... + 1 / NK-1-M + 1-R（ m）/ nk-m + 1 - r（m-1）/ n（k-1m + 1），其中m是侧面信息消息的数量，Ri是与Sigma缓存的ITH侧面信息消息的一部分（ m）（i）r（i）= s。基于此容量结果，我们证明了两个事实：首先，对于固定的内存大小s和固定数量的可访问消息m，统一的缓存达到最低标准化下载成本，即R（i）= s / m，对于i = 1，...，m是最佳的。其次，对于固定内存大小S，在所有可能的K-[S] + 1均匀高速缓存方案中，缓存M = k消息的均匀高速缓存方案实现了最低标准化下载成本。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号