ВЫЧИСЛИТЕЛЬНО-ЭФФЕКТИВНЫЙ ПРОТОКОЛ КОНФИДЕНЦИАЛЬНОГО ИЗВЛЕЧЕНИЯ ИНФОРМАЦИИ

Предложен новый вычислительно-эффективный протокол конфиденциального извлечения информации из удаленной базы данных. Основное достоинство предлагаемого решения состоит в низкой вычислительной сложности процедуры извлечения информации, а также в конструктивной простоте и гибкости выбора параметров системы. Результаты получены благодаря использованию свойств орбит действия групп Галуа конечных расширений поля GF(q). Наилучшим существующим на данный момент кодовым решениям схема уступает по коммуникационной сложности незначительно, но при этом имеет конструктивную процедуру построения для любых допустимых параметров. По сравнению с существующими решениями, основанными на свойствах полиномов, предложенный протокол имеет меньшую вычислительную сложность, что, безусловно, является важным фактором для серверной части, которая должна обслуживать множественные заявки.

1. Chor B., Kushilevitz E., Goldreich O., Sudan M. Private information retrieval // Proc. 36th Annual IEEE Symp. Foundation of Computer Science. Milwaukee, USA, 1995. P. 41–50.
2. Chor B., Gilboa N. Computationally private information retrieval // Proc. 29th Annual ACM Symposium on Theory of Computing. El Paso, USA, 1997. P. 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. P. 364–373.
4. Cachin C., Micaliy S., Stadlerz M. Computationally private information retrieval with polylogarithmic communication // Lecture Notes in Computer Science. 1999. V. 1592. P. 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. V. 3108. P. 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. P. 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. V. 40. N 3. P. 683–695.
9. Asonov D., Freytag J.C. Almost optimal private information retrieval // Proc. 2nd Workshop on Privacy Enhancing Technologies. 2002. V. 2482. P. 209–223.
10. Ambainis A. Upper bound on the communication complexity of private information retrieval // Lecture Notes in Computer Science. 1997. V. 1256. P. 401–407.
11. Yekhanin S. Locally decodable codes // Lecture Notes in Computer Science. 2011. V. 6651. P. 289–290.
12. Woodruff D., Yekhanin S. A geometric approach to information-theoretic private information retrieval // SIAM Journal of Computing. 2007. V. 37. N 4. P. 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. V. 71. N 2. P. 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. P. 261–270.
15. Shamir A. How to share a secret // Communications of the ACM. 1979. V. 22. N 11. P. 612–613. doi: 10.1145/359168.359176
 

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License