Sergey Yekhanin
Skip Abstract Section
Abstract
Cryptographic protocols safeguard the privacy of user queries to public databases.
- Ambainis, A. Upper bound on the communication complexity of private information retrieval. In Proceedings of the Automata, Languages and Programming, 24th International Colloquium LNCS 1256 (Bologna, Italy, July 7--11). Springer, 1997, 401--407. Google Scholar
Digital Library
- Babai, L., Fortnow, L., Levin, L., and Szegedy, M. Checking computations in polylogarithmic time. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (New Orleans, LA, May 5--8). ACM Press, New York, 1991, 21--31. Google ScholarDigital Library
- Beimel, A., Ishai, Y., and Kushilevitz, E. General constructions for information-theoretic private information retrieval. Journal of Computer and System Sciences 71, 2 (2005), 213--247. Google ScholarDigital Library
- Beimel, A., Ishai, Y., Kushilevitz, E., and Raymond, J.F. Breaking the O (n1/(2k−1)) barrier for information-theoretic private information retrieval. In Proceedings of the 43rd Symposium on Foundations of Computer Science (Vancouver, B.C., Nov. 16--19). IEEE Computer Society, 2002, 261--270. Google ScholarDigital Library
- Beimel, A., Ishai, Y., and Malkin, T. Reducing the servers' computation in private information retrieval: PIR with preprocessing. In Proceedings of the 20th Annual International Cryptology Conference LNCS 1880 (Santa Barbara, CA, Aug. 20--24). Springer, 2000, 55--73. Google ScholarDigital Library
- Cachin, C., Micali, S., and Stadler, M. Computationally private information retrieval with polylogarithmic communication. In Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques LNCS 1592 (Prague, Czech Republic, May 2--6). Springer, 1999, 402--414. Google ScholarDigital Library
- Chor, B., Goldreich, O., Kushilevitz, E., and Sudan, M. Private information retrieval. Journal of the ACM 45, 6 (1998), 965--981. Google ScholarDigital Library
- Efremenko, K. 3-query locally decodable codes of subexponential length. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (Bethesda, MD, May 31--June 2). ACM Press, New York, 2009, 39--44. Google ScholarDigital Library
- Gasarch, W. Web page on private information retrieval; http://www.cs.umd.edu/gasarch/pir/pir.htmlGoogle Scholar
- Gentry, C. and Ramzan, Z. Single-database private information retrieval with constant communication rate. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming LNCS 3580 (Lisbon, Portugal, July 11--15). Springer, 2005, 803--815. Google ScholarDigital Library
- Ishai, Y., Kushilevitz, E., Ostrovsky, R., and Sahai, A. Batch codes and their applications. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (Chicago, June 13--16). ACM Press, New York, 2004, 262--271. Google ScholarDigital Library
- Itoh, T. and Suzuki, Y. New constructions for query-efficient locally decodable codes of subexponential length. IEICE Transactions on Information and Systems E93-D, 2 (2010), 263--270.Google Scholar
- Katz, J. and Trevisan, L. On the efficiency of local decoding procedures for error-correcting codes. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (Portland, OR, May 21--23). ACM Press, New York, 2000, 80--86. Google ScholarDigital Library
- Kerenidis, I. and de Wolf, R. Exponential lower bound for 2-query locally decodable codes via a quantum argument. Journal of Computer and System Sciences 69, 3 (2004), 395--420. Google ScholarDigital Library
- Kushilevitz, E. and Ostrovsky, R. Replication is not needed: Single-database computationally private information. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science (Miami Beach, FL, Oct. 19--22). IEEE Computer Society, 1997, 364--373. Google ScholarDigital Library
- Lipmaa, H. An oblivious transfer protocol with log-squared communication. In Proceedings of the 11th International Conference on Information Security LNCS 5222 (Taipei, Sept. 15--18). Springer, 2008, 314--328. Google ScholarDigital Library
- Ostrovsky, R. and Sketch, W.E. III A survey of single database private information retrieval: Techniques and applications. In Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography LNCS 4450 (Beijing, Apr. 16--20). Springer, 2007, 393--411. Google ScholarDigital Library
- Raghavendra, P. A Note on Yekhanin's Locally Decodable Codes Technical Report TR07-016. Electronic Colloquium on Computational Complexity, 2007.Google Scholar
- Sudan, M. Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems. Ph.D. thesis, University of California, Berkeley, 1992. Google ScholarDigital Library
- Trevisan, L. Some applications of coding theory in computational complexity. Quaderni di Matematica 13 (2004), 347--424.Google Scholar
- Wehner, S. and de Wolf, R. Improved lower bounds for locally decodable codes and private information retrieval. In Proceedings of the 32nd International Colloquium on Automata, Languages, and Programming LNCS 3580 (Lisbon, Portugal, July 11--15). Springer, 2005, 1424--1436. Google ScholarDigital Library
- Woodruff, D. New Lower Bounds for General Locally Decodable Codes Technical Report TR07-006. Electronic Colloquium on Computational Complexity, 2007.Google Scholar
- Woodruff, D and Yekhanin, S. A geometric approach to information theoretic private information retrieval. SIAM Journal on Computing 47, 4 (2007), 1046--1056. Google ScholarDigital Library
- Yekhanin, S. Towards 3-query locally decodable codes of subexponential length. Journal of the ACM 55, 1 (2008), 1--14. Google ScholarDigital Library
- Yekhanin, S. Locally Decodable Codes and Private Information Retrieval Schemes. Ph.D. thesis. Massachusetts Institute of Technology, Cambridge, MA, 2007; http://research.microsoft.com/en-us/um/people/yekhanin/Papers/phdthesis.pdf Google ScholarDigital Library
Index Terms
- Private information retrieval
Recommendations
Outsourced private information retrieval
WPES '13: Proceedings of the 12th ACM workshop on Workshop on privacy in the electronic societyWe propose a scheme for outsourcing Private Information Retrieval (PIR) to untrusted servers while protecting the privacy of the database owner as well as that of the database clients. We observe that by layering PIR on top of an Oblivious RAM (ORAM) ...
Private information retrieval
CERIAS '15: Proceedings of the 16th Annual Information Security SymposiumPrivate Information Retrieval(PIR) is an important subject in the field of Information Retrieval. PIR allows two parties to communicate without revealing the information to one of the parties. The goal of our project is to implement a Private ...
Comments