Nikiforov
Vladimir O.
D.Sc., Prof.
doi: 10.17586/2226-1494-2016-16-2-290-294
COMPUTATIONALLY EFFICIENT PRIVATE INFORMATION RETRIEVAL PROTOCOL
Read the full article
';
For citation: Afanasyeva A.V., Bezzateev S.V. Сomputationally efficient private information retrieval protocol. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2016, vol. 16, no. 2, pp. 290–294, doi:10.17586/2226-1494-2016-16-2-290-294
Abstract
This paper describes a new computationally efficient private information retrieval protocol for one q-ary symbol retrieving. The main advantage of the proposed solution lies in a low computational complexity of information extraction procedure, as well as the constructive simplicity and flexibility in choosing the system parameters. Such results are based on cosets properties. The proposed protocol has communication complexity slightly worse than the best schemes at the moment, which is based on locally decodable codes, but it can be easily built for any parameters of the system, as opposed to codes. In comparison with similar solutions based on polynomials, the proposed method gains in computational complexity, which is important especially for servers which must service multiple requests from multiple users.
References
1. Chor B., Kushilevitz E., Goldreich O., Sudan M. Private information retrieval. Proc. 36th Annual IEEE Symp. Foundation of Computer Science. Milwaukee, USA, 1995, pp. 41–50.
2. Chor B., Gilboa N. Computationally private information retrieval. Proc. 29th Annual ACM Symposium on Theory of Computing. El Paso, USA, 1997, pp. 304–313.
3. Kushilevitz E., Ostrovsky R. Replication is not needed: single database, computationally-private information retrieval. Proc. 38th IEEE Annual Symposium on Foundations of Computer Science. Miami Beach, USA, 1997, pp. 364–373.
4. Cachin C., Micaliy S., Stadlerz M. Computationally private information retrieval with polylogarithmic com-munication. Lecture Notes in Computer Science, 1999, vol. 1592, pp. 402–414. doi: 10.1007/3-540-48910-X_28
5. Chang Y.-C. Single database private information retrieval with logarithmic communication. Lecture Notes in Computer Science, 2004, vol. 3108, pp. 50–61. doi: 10.1007/978-3-540-27800-9_5
6. Gentry C., Ramzan Z. Single-database private information retrieval with constant communication rate. Proc. 32th International Colloquium on Automata, Languages and Programming. Lisbon, Portugal, 2005, pp. 803–815.
7. Melchor C., Gaborit P. A lattice-based computationally-efficient private information retrieval protocol. IACR Cryptology ePrint Archive, 2007.
8. Smith S.W., Safford D. Practical server privacy with secure coprocessors. IBM Systems Journal, 2001, vol. 40, no. 3, pp. 683–695.
9. Asonov D., Freytag J.C. Almost optimal private information retrieval. Proc. 2nd Workshop on Privacy Enhancing Technologies, 2002, vol. 2482, pp. 209–223.
10. Ambainis A. Upper bound on the communication complexity of private information retrieval. Lecture Notes in Computer Science, 1997, vol. 1256, pp. 401–407.
11. Yekhanin S. Locally decodable codes. Lecture Notes in Computer Science, 2011, vol. 6651, pp. 289–290.
12. Woodruff D., Yekhanin S. A geometric approach to information-theoretic private information retrieval. SIAM Journal of Computing, 2007, vol. 37, no. 4, pp. 1046–1056. doi: 10.1137/06065773X
13. Beimel A., Ishai Y., Kushilevitz E. General constructions for information-theoretic private information retrieval. Journal of Computer and System Sciences, 2005, vol. 71, no. 2, pp. 213–247. doi: 10.1016/j.jcss.2005.03.002
14. Beimel A., Ishai Y., Kushilevitz E., Raymond J.F. Breaking the O(n1/(2k-1)) barrier for information-theoretic private information retrieval. Proc. 43rd Annual IEEE Symposium on Foundations of Computer Science. Vancouver, Canada, 2002, pp. 261–270.
15. Shamir A. How to share a secret. Communications of the ACM, 1979, vol. 22, no. 11, pp. 612–613. doi: 10.1145/359168.359176
