• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Computing >A geometric approach to information-theoretic private information retrieval
【24h】

A geometric approach to information-theoretic private information retrieval

机译：信息论私人信息检索的几何方法

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

摘要

A t-private private information retrieval (PIR) scheme allows a user to retrieve the ith bit of an n-bit string x replicated among k servers, while any coalition of up to t servers learns no information about i. We present a new geometric approach to PIR and obtain the following: (1) A t-private k-server protocol with communication O(k(2)/t logk n(1/[(2k-1)/t])), removing the kt term of previous schemes. This answers an open question of [Y. Ishai and E. Kushilevitz, in Proceedings of the 31st ACM Symposium on Theory of Computing, 1999, pp. 79-88]. (2) A 2-server protocol with O(n1/3) communication, polynomial preprocessing, and online work O(n/log(r) n) for any constant r. This improves the O(n/log(2) n) work of [A. Beimel, Y. Ishai, and T. Malkin, J. Cryptology, 17 (2004), pp. 125-151]. (3) Smaller communication for instance hiding [D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway, J. Cryptology, 10 (1997), pp. 17-36; Y. Ishai and E. Kushilevitz, in Proceedings of the 31st ACM Symposium on Theory of Computing, 1999, pp. 79-88], PIR with a polylogarithmic number of servers, and robust PIR [A. Beimel and Y. Stahl, in Proceedings of the 3rd Conference on Security in Communications Networks (SCN 2002), Lecture Notes in Comput. Sci. 2576, Springer, Berlin, 2003, pp. 326-341].
机译：T私有信息检索（PIR）方案允许用户检索在k台服务器之间复制的n位字符串x的第i位，而最多t台服务器的任何联盟都不了解有关i的信息。我们提出一种新的PIR几何方法，并获得以下信息：（1）通信为O（k（2）/ t logk n（1 / [（2k-1）/ t]））的t私有k服务器协议，删除先前方案的kt项。这回答了[Y. Ishai和E. Kushilevitz，在第31届ACM计算理论研讨会论文集中，1999，第79-88页。 （2）2服务器协议，具有O（n1 / 3）通信，多项式预处理和在线工作O（n / log（r）n），用于任何常数r。这提高了[A.的O（n / log（2）n）的工作。 Beimel，Y.Ishai和T.Malkin，J.Cryptology，17（2004），第125-151页。 （3）较小的通信，例如隐藏[D. Beaver，J.Feigenbaum，J.Kilian，和P.Rogaway，J.Cryptology，10（1997），第17-36页;和J.C. Y. Ishai和E. Kushilevitz，在“第31届ACM计算理论研讨会论文集，1999，第79-88页”中，具有多对数服务器的PIR和可靠的PIR [A. Beimel和Y. Stahl，在“第三届通信网络安全性会议（SCN 2002）”的会议记录中，在Comput.com上发表演讲。科学2576，施普林格，柏林，2003年，第326-341页。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号