Коммуникационная сложность протоколов доступа к данным без раскрытия запроса

В связи с постоянным расширением области применения компьютерных технологий, одним из актуальных направлений дискретной математики и математической кибернетики являются операции хранения и поиска информации. В последние десятилетия активно развивается новое научное направление, связанное с оптимальным хранением и поиском информации, именуемое теорией информационного поиска. Одним из главных носителей этого направления является теория баз данных [28, Э. Э. Гасанов, 1985 г.],[29, Э. Э. Гасанов, В. Б. Кудрявцев, 2002 г.]. В данной работе рассматривается одна из составляющих данной теории — проблема защищенности баз данных и поисковых систем, а именно проблема защиты информации в интересах пользователей.

В настоящее время знание некоторых предпочтений пользователей приобретает известное значение и цену. С другой стороны, нет никаких оснований считать, что администратор сервера, на котором хранится база данных, не использует информацию о своем пользователе против его самого.

Протоколы извлечения информации без раскрытия запроса позволяют пользователю получить желаемый бит информации из базы данных таким образом, что администратор базы данных ничего не узнает о номере бита, который запрашивал пользователь. Понятие такого протокола впервые было введено в работе [12, В. Chor, О. Goldreich, Е. Kushilevitz, М. Sudan, 1995 г.] под названием Private Information Retrieval, поэтому мы в дальнейшем будем называть такие протоколы PIR-протоколами.

Существует множество примеров, где использование протоколов, которые скрывают от администраторов базы данных интересы их пользователей (PIR-протоколов), может быть полезно.

Фармацевтические базы данных. Обычно фармацевтические компании специализируются либо в изобретении новых лекарств, либо на сборе информации об определенных компонентах и их свойствах (фармацевтические базы данных). Процесс получения нового лекарства заключает в себе необходимость получения информации из базы данных о его компонентах. Чтобы скрыть планы компании, можно купить целую базу данных. В этом случае PIR-протоколы позволяют избежать огромных затрат.

Учебные примеры. Специальный отдел министерства обороны планирует секретную операцию в регионе X. Чтобы получить карту региона он должен сделать запрос в базу данных карт. Таким образом, может произойти утечка данных о том, что скоро произойдет секретная операция в регионе X. Возможно, конечно, в целях безопасности, купить всю базу данных карт. Опять же, этого возможно избежать при использовании протоколов PIR.

Таким образом, существуют примеры, когда необходима защита интересов пользователей баз данных. До недавнего времени этот вопрос не учитывался при их построении.

Существует простое решение, когда сервер передает всю базу данных пользователю. Но если считать, что пользователь платит за количество всех принятых и переданных за время протокола бит, то цена такого протокола очень высока. Назовем коммуникационной сложностью PIR-протокола общее количество бит, которыми обмениваются участники за время протокола. Тогда целью построения PIR-протоколов является построение протоколов с минимальной коммуникационной сложностью.

В работе [12, В. Chor, О. Goldreich, Е. Kushilevitz, М. Sudan, 1995 г.] было показано, что если база данных хранится на одном сервере, то минимальная коммуникационная сложность PIR-протокола равна длине базы данных. Чтобы решить эту проблему, было предложено копировать базу данных на к несообщающихся между собой серверах, и проводить протокол таким образом, что каждый отдельный сервер не получает никакой информации об индексе бита, который хотел узнать пользователь.

Рассмотрим протокол с к + 1 участником: пользователем и к несообщающимися серверами (к > 1), причем каждый из серверов хранит один и тот же булев вектор х = (Xq,. ,?n-i) длины п — базу данных. Пользователь желает узнать значение г-го бита хг этого вектора так, чтобы номер бита i не стал известен ни одному из серверов. Протокол состоит из следующих шагов.

1) Пользователь имеет номер бита г и вырабатывает случайное число г. По числам гиг пользователь вычисляет с помощью специальной функции, называемой функцией запросов, к чисел д-7 и посылает j-му серверу запрос qj•.

2) Каждый из к серверов по полученному запросу qi и базе данных х с помощью специальной функции ответов вычисляет вектор ai и посылает его пользователю.

3) Пользователь по числам i, г и fc ответам серверов а-7 вычисляет с помощью реконструирующей функции нужный бит Х{.

Первое требование к протоколу состоит в том, что ни один из серверов по своему запросу д-7 не может понять, с помощью какого бита г этот запрос был порожден. Это требование называется требованием защищенности. Второе требование к протоколу, называемое требованием корректности, заключается в том, что пользователь по ответам серверов правильно восстанавливает бит Х{. Предполагается, что всем участникам протокола — и пользователю и серверам — известны функции запросов, ответов и реконструирующая. Но серверам не известно случайное число г и, разумеется, не известен номер бита i. Целью построения PIR-протоколов является построение протокола с минимальной коммуникационной сложностью для заданных пик.

Наиболее известные результаты были приведены в [27, S. Yekhanin, 2006], [26, Alexander A. Razborov, Sergey Yekhanin, 2006], [6, A. Beimel, Y. Ishai, E. Kushilevitz, J.-F.Raymond, 2002 г.], в [20, O. Goldreich, H. Karloff, L. Schulman, L. Trevisan, 2002] и в [24, I. Kerendis и R. de Wolf, 2003].

Известно, что всегда существует простейший PIR-протокол, коммуникационная сложность которого равна длине базы данных п. В этом протоколе каждый сервер выдает пользователю свою часть базы данных, а пользователь, собрав всю базу данных извлекает нужный бит. PIR-протокол, у которого коммуникационная сложность больше либо равна длине базы данных, будем считать вырожденным.

В работе впервые была предложена и решена проблема принадлежности PIR-протокола к классу невырожденных PIR-протоколов по основным параметрам.

Впервые была получена нижняя оценка коммуникационной сложности для класса PIR-протоколов с более чем 2-мя серверами. Также впервые была получена нетривиальная точная оценка коммуникационной сложности PIR-протоколов.

Также в данной работе был получена оценка коммуникационной сложности для более широкого класса PIR-протоколов, чем в известных работах по этой тематике. Во-первых, в отличие от полученных ранее известных результатов, мы не предполагали, что длины ответов серверов должны быть равны между собой, во-вторых, мы не налагаем никаких ограничений на количество бит, которые пользователь использует из ответов серверов. В-третьих, получена нижняя оценка, которая не налагает ограничений на линейность функций PIR-протокола. И наконец, полученная нижняя оценка коммуникационной сложности по порядку совпадает с коммуникационной сложностью наилучшего известного на сегодняшний момент PIR-протокола для к = 2, к > 3 серверов. Также заметим, что для доказательства известных нижних оценок, авторы [20, O. Goldreich, H. Karloff, L. Schulman, L. Trevisan, 2002] использовали сведение PIR-протоколов к LDC-протоколам, а авторы [24, I. Kerendis и R. de Wolf, 2003] использовали сведение PIR-протоколов к квантовым PIR-протоколам. Полученная нами нижняя оценка коммуникационной сложности PIR-протоколов доказана напрямую для PIR-протоколов.

Поскольку во всех известных PIR-протоколах, в результате каждого запроса пользователь, помимо запрашиваемого бита, получает много дополнительной информации о других битах базы данных, он может получить всю базу данных за количество запросов, меньшее ее длины. Степенью раскрытия PIR-протоколом базы данных назовем число шагов, за которое пользователь может вычислить всю базу данных. В работе исследуется степень раскрытия известных PIR-протоколов, а также построенных в данной работе PIR-протоколов. Приведем формальное определение PIR-протокола.

Для любого натурального п обозначим Еп = {0,., п — 1}. Пусть к, 7 г, s, т, р°,., рк~1 — натуральные числа, р = р° +. + рк~г. Пусть на множестве В — {(г, г), г G Еп, г 6 Е3} задано вероятностное пространство < В, 2s, Р >, где Р (г, г) = для любых i G Еп: г Е Es. Тогда (k, n, s, m, p) PIR-протоколом называется набор из к + 2 функций I = (Q, А0,., Ak~l, R), где Q, А0,., Ak~l, R некоторые отображения, Q: Ек х Еп х Ея -> Ет, А*: Ет х {0,1}п {0,1}^, j G Ек,.

R: En xEs x {0,1}P —" {0,1}, такие, что выполнено 2 условия:

• корректности: для любых % Е Еп, г? Es выполнено.

R{i, г, A°(Q (0, г, г), ж),., Ak~l{Q{k — 1, г, т), х)) = а*;

• защищенности: для любых q Е Ет, t Е г, j Е Еп выполнено.

P (Q (t, i, r) = g) = P (Q (t, j, r) = 9).

Здесь и везде далее /с — число серверовп — длина базы данных х = (хо, xi,., Xn-i) — s ~ параметр датчика случайных чисел, точнее датчик случайных чисел дает равновероятно числа из множества-Е1, — т — характеристика функции запросов Q, точнее функция запросов Q принимает значения из Етpi — количество бит в ответе j-ro сервера, А> — функция ответа j-ro сервера (j Е Е^)', R — реконструирующая функция.

Содержательно протокол / = (Q, А0,., Ак~11 R) состоит из следующих шагов:

• Пользователь, имея запрос г, вырабатывает случайное число г Е Es, для каждого j Е Ek вычисляет qi = Q (j, i, r) и посылает gJ серверу.

• Каждый сервер Sj, j Е Ek, вычисляет о7 — (aJ0,., a^J = AJ (qi, x) и посылает вектор aJ пользователю.

• Пользователь вычисляет Xi — R (i, г, a0,., ак~1).

Если d — вещественное число, то через ]d[ обозначим наименьшее целое не меньшее, чем d, а через [d] — наибольшее целое не большее, чем d.

Величина С (1) = к) log2 т[+р называется коммуникационной сложностью протокола I, и представляет собой число бит, переданных в процессе протокола.

Условие корректности гарантирует, что пользователь получит нужный бит базы данных, а условие защищенности — что ни один из серверов по вектору q, который он получил, не сможет понять какой бит интересует пользователя.

СОДЕРЖАНИЕ РАБОТЫ.

1. A. Ambainis. Upper bound on the communication complexity of private information retrieval. 1. Proc. of 24th ICALP, 1997.

2. D. Asonov. Private information retrieval. In GI Jahrestagung (2), pages 889 894, 2001.

3. D. Asonov and J.C. Freytag. Almost optimal private information retrieval n 2nd Workshop on Priacy Enhancing Technologies (PET2002), 2002.

4. A. Beimel, Y. Ishai, and T. Malkin. Reducing the servers computation in private information retrieval: PIR with preprocessing. In Proc. of CRYPTO’OO, 2000.

5. A. Beimel and Y. Ishai. Information-theoretic private information retrieval: A unified construction. ECCC Report TR01−015, Feb. 2001.

6. A. Beimel, Y. Ishai, E. Kushilevitz, and J. F. Raymond. Breaking the 0(n1//2fc1) barrier for inforamtiontheoretic private information retrieval. In Proc. of the 43st IEEE Sym. on Found, of Comp.Sci., 2002.

7. A. Beimel, Y. Ishai and E. Kushilevitz and E.Kushilevitz. General constructions for information-theoretic private information retrieval, 2003.

8. G. Blazzard, C. Crepeau and J.-M Robert. All-or-nothing Disclosure of secrets. In Crypto'86 Springer-verlag, 1987, pp.234−238.

9. C. Blundo, P. D'Arco and A. De Santis. A^-Private /с-Database Private Information Retrieval Scheme. '2002.

10. R. Beigel, L. Fortnow, and W.Gasarch. A nearly tight lower bound for private information retrieval protocols. Technical Report TR03−087, Electronic Colloquim on Computational Complexity (ECCC), 2003.

11. Cachin, S. Micali, and M. Stadler. Computationally private information retrieval with polylogarithmic communication. In Proc. of EUROCRYPT'99,1999.

12. B. Chor, 0. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. In Proc. of the 36th Annu. IEEE Symp. on Foundations of Computer Science, pages 41−51, 1995.

13. B. Chor, 0. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. Journal version: J. of the ACM, 45:965−981, 1998.

14. B. Chor and N. Gilboa. Computationally private information retrieval. In Proc. of 29th STOC, 1997. B. Chor and N. Gilboa. E.

15. G. D. Crescenzo, T. Malkin, and R. Ostrovsky. Single database private information retrieval implies oblivious transfer. In Proc. of EUROCRYPT’OO, 2000.

16. G. D. Crescenzo, Y. Ishai, and R. Ostrovsky. Universal service-providers for private information retrieval. Journal of Cryptology, 14(1), 2001. Earlier Version in PDS 1998.

17. S. Even, 0. Goldreich, and a.Lempecl. A randomized Protocol for Signing Contracts. Comm. of ACM, 28:537−647, 1985.

18. W. Gasarch. A survey on private information retrieval. Bull. Europ. Assoc. Theor. Comput. Sci. 82, 84−102, 2004.

19. Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin. Protecting data privacy in private information retrieval schemes. In Proc. of 30th STOC, 1998.

20. O. Goldreich, H. karloff, L. Schulman, and L.Trevisan. Lower bounds for linear locally decodable codes and private information retrieval systems. In Proc. of the 17th IEEE Conf. on Complexity Theory. IEEE Computer Society Press, 2002.

21. Y. Ishai and E.Kushilevitz. Private Simultaneous Messages Protocols with Applications. '1997.

22. Y. Ishai and E.Kushilevitz. Improved upper bounds on information-theoretic private information retrieval. In Proc of the 21th ACM Sym on Theory of Computing, 1999.

23. T.Itoh. On lower bounds for the communication complexity of private information retrieval. IEICE Trans. Fundamentals, ES40A (1), 2001.

24. I. Kerendis and R. de Wolf. Exponential lower bound for 2-query locally decodable codes. In Proc. of the 35th ACM Sym. on Theory of Computing, pages 106−115, 2003.

25. Kushilevitz and R. Ostrovsky. Replication is NOT needed: Single-database computationally private information retrieval. In Proc. of 38th FOCS, 1997. Report RC-21 851, IBM T.J. Watson Research Center, Oct. 2000.

26. Alexander A. Razborov, Sergey Yekhanin. An Omega (nl/3) Lower Bound for Bilinear Group Based Private Information Retrieval. FOCS 2006: 739−748.

27. S. Yekhanin. New Locally Decodable Codes and Private Information Retrieval Schemes, Electronic Colloquium on Computational Complexity (ECCC), TR06−127.

28. Гасанов Э. Э. О сложности информационного поиска, канд. дисс. Москва, 1985.

29. Гасанов Э. Э., Кудрявцев В. Б. Теория хранения и поиска информации. Москва, ФИЗМАТ ЛИТ, 2002.

30. Гасанов Э. Э., Майлыбаева Г. А. Доступ к базам данных без раскрытия запроса. Материалы конференции «Математика и безопасные информационные технологии Москва, 23−24 октября 2003 г., 393−395.

31. Ильин В. А., Поздняк Э. К., Линейная алгебра. М.:Наука, ФИЗМАТ-ЛЕТ, 1999.

32. Кудрявцев В. В., Алешин С. А., Подколзин А. С.

Введение

в теорию автоматов. М.:Наука, 1985.

33. Лупанов О. Б. О синтезе некоторых классов управляющих систем. Проблемы кибернетики. 1963. -Т.10. — С.63−97.

34. Яблонский С. В., Лупанов О. Б. Дискретная математика и математические вопросы кибернетики, том 1, Москва, Наука, 1974Работы автора по теме диссертации.

35. Гасанов Э. Э., Майлыбаева Г. А. Доступ к базам данных без раскрытия запроса. Материалы конференции «Математика и безопасные информационные технологии Москва, 23−24 октября 2003 г., 393−395.

36. Майлыбаева Г. А. Границы вырожденности протоколов доступа к данным без раскрытия запроса. Дискретная математика (2006) 18, N 2, 98 110.

37. Maylybaeva G.A. Degeneracy bounds for private information retrieval protocols. Discrete Mathematics and Applications, Volume 16, Number 3, 2006, pp. 245−257.

38. Майлыбаева Г. А. Оценки коммуникационной сложности линейных PIR-протоколов. Интеллектуальные системы, (2005) 9, № 1−4, 561−562.

39. Gulnara A. Maylybaeva, Communication complexity for a special class of private information retrieval protocols, In proc. of ICM2006, August (2006), pp. 499.

40. Майлыбаева Г. А. Коммуникационная сложность протоколов доступа к данным без раскрытия запросов. Материалы IX Международной конференции «Интеллектуальные системы и компьютерные науки» (Москва, 23−27 октября 2006 г.), том 1, часть 1, с. 181−183.

41. Майлыбаева Г. А. Точное значение коммуникационной сложности для одного класса PIR-протоколов. Интеллектуальные системы, (2007) 11, № 1−4, 167−200.

42. Майлыбаева Г. А. Порядок коммуникационной сложности PIR-протоколов. Интеллектуальные системы, (2007) 11, № 1−4, 729−732.

43. Майлыбаева Г. А. Порядок коммуникационной сложности для одного класса PIR-протоколов. Дискретная математика.