Zeev Dvir
ABSTRACT
A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the ith bit of an n-bit database replicated among two non-communicating servers, while not revealing any information about i to either server. In this work we construct a 2-server PIR scheme with total communication cost nO√(log log n)/(log n). This improves over current 2-server protocols which all require Ω(n1/3) communication. Our construction circumvents the n1/3 barrier of Razborov and Yekhanin which holds for the restricted model of bilinear group-based schemes (covering all previous 2-server schemes). The 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.
- A. Ambainis. Upper bound on communication complexity of private information retrieval. In ICALP, pages 401--407, 1997. Google Scholar
Digital Library
- A. Beimel and Y. Ishai. Information-theoretic private information retrieval: A unified construction. In ICALP, pages 912--926, 2001. Google ScholarDigital Library
- A. Beimel, Y. Ishai, E. Kushilevitz, and J.-F. Raymond. Breaking the o(n1/(2k-1)) barrier for information-theoretic private information retrieval. In FOCS, pages 261--270, 2002. Google ScholarDigital Library
- A. Bhowmick, Z. Dvir, and S. Lovett. New Bounds for Matching Vector Families. In Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing, STOC '13, pages 823--832, 2013. Google ScholarDigital Library
- Y. M. Chee, T. Feng, S. Ling, H. Wang, and L. F. Zhang. Query-efficient locally decodable codes of subexponential length. Computational Complexity, 22(1):159--189, 2013. Google ScholarDigital Library
- B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan. Private information retrieval. J. ACM, 45(6):965--981, 1998. Google ScholarDigital Library
- Z. Dvir, P. Gopalan, and S. Yekhanin. Matching vector codes. In FOCS, pages 705--714, 2010. Google ScholarDigital Library
- Z. Dvir and G. Hu. Matching-vector families and LDCs over large modulo. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (RANDOM-APPROX), volume 8096, pages 513--526. Springer Berlin Heidelberg, 2013.Google ScholarCross Ref
- K. Efremenko. 3-query locally decodable codes of subexponential length. In STOC, pages 39--44, 2009. Google ScholarDigital Library
- W. Gararch. A webpage on private information retrieval. https://www.cs.umd.edu/gasarch/TOPICS/pir/pir.html.Google Scholar
- W. I. Gasarch. A survey on private information retrieval (column: Computational complexity). Bulletin of the EATCS, 82:72--107, 2004.Google Scholar
- V. Grolmusz. Superpolynomial size set-systems with restricted intersections mod 6 and explicit ramsey graphs. Combinatorica, 20:2000, 1999.Google Scholar
- B. Hurley and T. Hurley. Group ring cryptography. CoRR, abs/1104.1724, 2011.Google Scholar
- T. Itoh and Y. Suzuki. Improved constructions for query-efficient locally decodable codes of subexponential length. IEICE Transactions, 93-D(2):263--270, 2010.Google Scholar
- D. Kahrobaei, C. Koupparis, and V. Shpilrain. Public key exchange using matrices over group rings. Groups-Complexity-Cryptology, 5(1):97--115, 2013.Google ScholarCross Ref
- J. Katz and L. Trevisan. On the efficiency of local decoding procedures for error-correcting codes. In 32nd ACM Symposium on Theory of Computing (STOC), pages 80--86, 2000. Google ScholarDigital Library
- I. Kerenidis and R. de Wolf. Exponential lower bound for 2-query locally decodable codes via a quantum argument. In STOC, pages 106--115, 2003. Google ScholarDigital Library
- H. Lipmaa. A webpage on oblivious transfer or private information retrieval. http://www.cs.ut.ee/lipmaa/crypto/link/protocols/oblivious.php.Google Scholar
- B. R. McDonald. Linear Algebra Over Commutative Rings. Pure and Applied Mathematics#87. Marcel Dekker, New York, 1984.Google Scholar
- R. Ostrovsky and W. E. S. III. A survey of single database PIR: techniques and applications. IACR Cryptology ePrint Archive, 2007:59, 2007.Google Scholar
- A. A. Razborov and S. Yekhanin. An Ω(n1/3) lower bound for bilinear group based private information retrieval. In FOCS, pages 739--748, 2006. Google ScholarDigital Library
- S. Wehner and R. de Wolf. Improved lower bounds for locally decodable codes and private information retrieval. In ICALP, pages 1424--1436, 2005. Google ScholarDigital Library
- D. P. Woodruff and S. Yekhanin. A geometric approach to information-theoretic private information retrieval. In IEEE Conference on Computational Complexity, pages 275--284, 2005. Google ScholarDigital Library
- S. Yekhanin. Towards 3-query locally decodable codes of subexponential length. J. ACM, 55(1), 2008. Google ScholarDigital Library
- S. Yekhanin. Locally decodable codes. Foundations and Trends in Theoretical Computer Science, 6(3):139--255, 2012. Google ScholarDigital Library
Index Terms
- 2-Server PIR with Sub-Polynomial Communication
Recommendations
2-Server PIR with Subpolynomial Communication
A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the ith bit of an n-bit database replicated among two noncommunicating servers, while not revealing any information about i to either server. In this work, we construct a 2-...
General constructions for information-theoretic private information retrieval
A Private Information Retrieval (PIR) protocol enables a user to retrieve a data item from a database while hiding the identity of the item being retrieved; specifically, in a t-private k-server PIR protocol the database is replicated among k servers, ...
On Locally Decodable Codes, Self-Correctable Codes, and t-Private PIR
A k-query locally decodable code (LDC) allows to probabilistically decode any bit of an encoded message by probing only k bits of its corrupted encoding. A stronger and desirable property is that of self-correction, allowing to efficiently recover not ...
Comments