首页    期刊浏览 2024年10月06日 星期日
登录注册

文章基本信息

  • 标题:2-Server PIR with sub-polynomial communication
  • 本地全文:下载
  • 作者:Zeev Dvir ; Sivakanth Gopi
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the i th bit of an n -bit database replicated among two servers (which do not communicate) while not revealing any information about i to either server. In this work we construct a 1-round 2-server PIR with total communication cost n O ( log log n log n ) . This improves over the currently known 2-server protocols which require O ( n 1 3 ) communication and matches the communication cost of known 3-server PIR schemes. Our improvement comes from reducing the number of servers in existing protocols, based on Matching Vector Codes, from 3 or 4 servers to 2. This is achieved by viewing these protocols in an algebraic way (using polynomial interpolation) and extending them using partial derivatives.

  • 关键词:Locally decodable codes ; private information retrieval
国家哲学社会科学文献中心版权所有