МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

им. M.В.Ломоносова

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи

УДК 519.712.3

Майлыбаева Гульнара Абаевна

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

данным без раскрытия запроса.

01.01.09 дискретная математика и математическая кибернетика автореферат диссертации на соискание ученой степени кандидата физико–математических наук

Научный руководитель доктор физико-математических наук профессор Э.Э.Гасанов Москва

Работа выполнена на кафедре математической теории интеллектуальных систем Механико-математического факультета Московского государственного университета имени М.В.Ломоносова.

Научный руководитель: доктор физико-математических наук, профессор Гасанов Эльяр Эльдарович

Официальные оппоненты: доктор физико-математических наук, профессор Ложкин Сергей Андреевич кандидат физико-математических наук Шакиров Абдыганы Абжамилович

Ведущая организация: Вычислительный Центр РАН

Защита диссертации состоится 18 апреля 2008 г. в 16 ч. 40 м. на заседании диссертационного совета Д.501.001.84 при Московском государственном университете им. М.В.Ломоносова по адресу: Российская Федерация, 119991, ГСП-1, Москва, Ленинские горы, МГУ, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 18 марта 2007 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ доктор физико-математических наук, профессор А.О.Иванов

Общая характеристика работы

Актуальность темы В связи с постоянным расширением области применения компьютерных технологий, одним из актуальных направлений дискретной математики и математической кибернетики являются операции хранения и поиска информации. В последние десятилетия активно развивается новое научное направление, связанное с оптимальным хранением и поиском информации, именуемое теорией информационного поиска. Одним из главных носителей этого направления является теория баз данных1,2. В данной работе рассматривается одна из составляющих данной теории – проблема защищенности баз данных и поисковых систем, а именно проблема защиты информации в интересах пользователей.

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

Протоколы извлечения информации без раскрытия запроса позволяют пользователю получить желаемый бит информации из базы данных таким образом, что администратор базы данных ничего не узнает о номере бита, который запрашивал пользователь. Понятие такого протокола впервые было введено в работе B. Chor, O. Goldreich, E. Kushilevitz и M. Sudan3 под названием Private Information Retrieval, поэтому мы в дальнейшем будем называть такие протоколы PIR-протоколами.

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

Фармацевтические базы данных. Обычно фармацевтические компании специализируются либо в изобретении новых лекарств, либо на Гасанов Э.Э. О сложности информационного поиска, канд. дисс. Москва, Гасанов Э. Э., Кудрявцев В.Б. Теория хранения и поиска информации. Москва, ФИЗМАТЛИТ, B. Chor, O. 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.

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

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

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

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

Тогда целью построения PIR-протоколов является построение протоколов с минимальной коммуникационной сложностью.

В работе B. Chor, O. Goldreich, E. Kushilevitz и M. Sudan4 было показано, что если база данных хранится на одном сервере, то минимальная коммуникационная сложность PIR-протокола равна длине базы данных.

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

B. Chor, O. 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.

Рассмотрим протокол с k + 1 участником: пользователем и k несообщающимися серверами (k 1), причем каждый из серверов хранит один и тот же булев вектор x = (x0,..., xn1 ) длины n базу данных.

Пользователь желает узнать значение i-го бита xi этого вектора так, чтобы номер бита i не стал известен ни одному из серверов. Протокол состоит из следующих шагов.

1) Пользователь имеет номер бита i и вырабатывает случайное число r.

По числам i и r пользователь вычисляет с помощью специальной функции, называемой функцией запросов, k чисел q j и посылает j-му серверу запрос 2) Каждый из k серверов по полученному запросу q j и базе данных x с помощью специальной функции ответов вычисляет вектор aj и посылает его пользователю.

3) Пользователь по числам i, r и k ответам серверов aj вычисляет с помощью реконструирующей функции нужный бит xi.

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

Приведем формальное определение PIR-протокола. Для любого натурального n обозначим En = {0,..., n 1}. Пусть k, n, s, m, p0,..., pk1 натуральные числа, p = p0 +... + pk1. Пусть на множестве B = {(i, r), i En, r Es } задано вероятностное пространство < B, 2B, P >, где P(i, r) = n·s, для любых i En, r Es. Тогда (k, n, s, m, p) PIRпротоколом называется набор из k + 2 функций I = Q, A0,..., Ak1, R, где Q, A0,..., Ak1, R некоторые отображения, Q : Ek En Es Em, Aj : Em {0, 1}n {0, 1}p, j Ek, R : En Es {0, 1}p {0, 1}, такие, что выполнены 2 условия:

• корректности: для любых i En, r Es выполнено • защищенности: для любых q Em, t Ek, i, j En выполнено Наиболее известные результаты по этой тематике были получены в работах: С.Еханина5, А.Разборова и С.Еханина6, Beimel, Y. Ishai, E. Kushilevitz и J. F. Raymond7, в O.Goldreich, H.karlo, L.Schulman и L.Trevisan 8 и в работе I.Kerendis и R. de Wolf9.

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

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

Известно, что всегда существует простейший PIR-протокол, коммуникационная сложность которого равна длине базы данных n. В S. Yekhanin. New Locally Decodable Codes and Private Information Retrieval Schemes, Electronic Colloquium on Computational Complexity (ECCC), TR06-127.

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

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

O.Goldreich, H.karlo, 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.

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.

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

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

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

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

Описанная в данной работе оценка коммуникационной сложности получена для более широкого класса PIR-протоколов, чем в известных работах по этой тематике. Во-первых, в отличие от полученных ранее результатов, мы не предполагали, что длины ответов серверов должны быть равны между собой, во-вторых, мы не налагаем никаких ограничений на количество бит, которые пользователь использует из ответов серверов. Втретьих, получена нижняя оценка, которая не налагает ограничений на линейность функций используемых в протоколе. И наконец, полученная нижняя оценка коммуникационной сложности по порядку совпадает с коммуникационной сложностью наилучшего известного на сегодняшний момент PIR-протокола для k = 2 серверов. Также заметим, что для доказательства известных нижних оценок, в работе O.Goldreich, H.karlo, L.Schulman и L.Trevisan 10 авторы использовали сведение PIR-протоколов к LDC-протоколам, а в работе I.Kerendis и R. de Wolf11 авторы использовали сведение PIR-протоколов к квантовым PIR-протоколам. Полученная нами нижняя оценка коммуникационной сложности PIR-протоколов доказана напрямую для PIR-протоколов.

Степенью существенности булевой функции f (x1,..., xl ) назовем число O.Goldreich, H.karlo, 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.

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.

переменных, от которых она существенно зависит, и обозначим его через S(f ).

Степенью существенности булевой вектор-функции назовем число A (q, x), Al (q, x), l Epj, j Ek, q Es также будем использовать следующую запись: Aj (q, x) = Aj (q)(x), Aj (q, x) = Aj (q)(x), где A (q) {0, 1} {0, 1} булева вектор-функция n переменных, Al (q) {0, 1} {0, 1} булева функция n переменных.

Степенью существенности функции ответов j-го сервера Aj : Es {0, 1}n {0, 1}p, j E2, назовем число Для любых i En, r Es определим следующую булеву функцию от p переменных: Ri,r : {0, 1}p {0, 1}, где Ri,r (a0,..., ak1 ) = R(i, r, a0,..., ak1 ).

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

1. Найдены границы вырожденности PIR-протоколов по основным параметрам: по количеству серверов; по мощности множества значений датчика случайных чисел; по мощности множества значений и степени существенности функции запросов; по степени существенности реконструирующей функции. В результате получен критерий принадлежности PIR-протокола к классу невырожденных PIRпротоколов.

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

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

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

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

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

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

Апробация работы. Результаты настоящей работы докладывались на семинарах механико-математического факультета МГУ им. М.В.Ломоносова:

на семинаре "Теория автоматов" под руководством академика, проф., д.фм.н. В.Б. Кудрявцева (2005-2007 гг.), на семинаре "Вопросы сложности алгоритмов поиска" под руководством проф., д.ф-м.н. Э.Э.Гасанова (2004гг.), на семинаре факультета вычислительной математики и кибернетики МГУ им. М.В.Ломоносова "Дискретная математика и математическая кибернетика"под руководством проф. В.Б. Алексеева, проф. А.А. Сапоженко, проф. С.А. Ложкина (2007 г.), на конференции "Математика и безопасные информационные технологии" (Москва, 2003 г.), на XIV Международной конференции по проблемам теоретической кибернетики (Пенза, 2005 г.), на первой, второй и третьей научной конференциях аспирантов кафедры МаТИС механико-математического факультета МГУ (Москва, 2005-2007 гг.), на Ломоносовских чтениях МГУ (Москва, 2005-2007 гг.), на международном математическом конгрессе "International Congress of Mathematics" (Мадрид, 2006 г.), на IX международной конференции "Интеллектуальные системы и компьютерные науки" (Москва, 2006 г.).

Публикации. Основные результаты диссертации опубликованы в работах автора, список которых приводится в конце автореферата [1-7].

Структура и объем работы. Диссертация состоит из введения, трех глав и приложения. Объем диссертации 109 стр. Список литературы содержит 43 наименования.

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

Также во введении описан метод практического применения PIR-протоколов.

В главе 1 исследуются границы вырожденности PIR-протоколов по основным параметрам. В частности, в разделе 1.1 приводится простейший вырожденный PIR-протокол, в разделе 1.2 приводится простейший невырожденный PIR-протокол. В разделах 1.3 - 1.8 приводятся доказательства утверждений о границах вырожденности PIR-протокола по основным параметрам: числу серверов, по длине датчика случайных чисел, по длине базы данных, по степени существенности функции ответов, по степени существенности реконструирующей функции.

Из утверждений 1.1 - 1.8 следует теорема о границах вырожденности PIRпротокола по основным параметрам.

Теорема 1. Для любого натурального n 12 невырожденный (k, n, s, m, p) PIR-протокол I = Q, A0,..., Ak1, R существует тогда и только тогда, когда одновременно выполнены следующие условия:

1. количество серверов k 2, 2. длина датчика случайных чисел s 2, 3. мощность множества запросов m 2, 4. существует такое j Ek, что выполнено S(Aj ) 2, 5. S(R) 2.

PIR-протоколы, для которых выполнено m = s будем обозначать четверкой параметров (k, n, s, p). Обозначим через I(k, n, s) класс всех (k, n, s, p) PIR-протоколов, где p > 0. Пусть A некоторое множество PIRпротоколов. Тогда обозначим Обозначим через Ad множество всех PIR-протоколов таких, что степень существенности функции ответов каждого сервера не превосходит d.

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

Раздел 2.1 посвящен исследованию коммуникационной сложности PIRпротоколов в классе A2 классе PIR-протоколов, степень существенности функции ответов которых не превосходит 2. Раздел 2.1.1 посвящен доказательству леммы о верхней оценке в данном классе, а именно в данном разделе построен PIR-протокол с заданными параметрами.

Лемма 1. Для любых натуральных n, s таких что s < n верно Назовем булеву функцией f (x1,..., xl ) линейной, если для любых x1, x {0, 1}, 1 t l верно Линейным (k, n, s, p) PIR-протоколом назовем такой PIR-протокол, у которого для любых j Ek, l pj, r, q Es, i En функции Aj (q) и Ri,r являются линейными функциями. Положим D2 множество всех линейных PIR-протоколов из класса A2. Проще говоря, для любого PIRпротокола из D2 верно: каждый бит ответа каждого сервера является суммой некоторых бит базы данных, и для того, чтобы получить значение искомого бита пользователь складывает некоторые биты ответов серверов. В разделе 2.1.2 доказывается, что в классе A2 для построения PIR-протоколов можно использовать только линейные функции.

Теорема 2. Для любого (2, n, s, p) PIR-протокола из класса A2, существует (2, n, s, p) PIR-протокол из класса линейных протоколов D2 с такой же коммуникационной сложностью.

В разделах 2.1.3 и 2.1.4 приведены примеры PIR-протоколов с мощностью датчика случайных чисел равного 2 и 3 соответственно.

В разделе 2.1.5 приводится доказательство леммы о нижней оценке коммуникационной сложности PIR-протоколов в классе A2.

Лемма 2. Для любых натуральных n, s таких что s < n верно Будем писать (n) = o(1), если lim (n) = 0; A(n) = o · (B(n)), если A(n) = B(n) · o(1). Скажем, что A(n) асимптотически не превосходит B(n) при n и обозначим A B, если существует (n) = o(1) такое, что начиная с некоторого номера n0, A(n) (1 + (n)) · B(n). Если A(n) B(n) и A(n) B(n), то будем говорить что A и B асимптотически равны при n и обозначать A B.

Из леммы 1 и 2 следует теорема об асимптотически точной оценке коммуникационной сложности PIR-протоколов в классе A2.

Теорема 3. Если s = o( n) при n, то при n верно и при n кратном s2 верно Раздел 2.2 посвящен исследованию коммуникационной сложности PIRпротоколов в классе Ad классе PIR-протоколов, степень существенности функции ответов которых не превосходит d. В разделе 2.2.1 приводится доказательство теоремы о верхней оценке коммуникационной сложности PIR-протоколов для k серверов, степень существенности функций ответов серверов которых не превосходит d, где 0 < d n2k2/2k1.

Лемма 3 (Верхняя оценка). Для любых натуральных k, n и d таких что 0 < d n2k2/2k1, верно В разделе 2.2.2 приводится пример PIR-протокола при d = n, s = 2 3.

В разделе 2.2.3 приводится доказательство теоремы о нижней оценке коммуникационной сложности PIR-протоколов для k серверов, степень существенности функций ответов серверов которых не превосходит d, где d – произвольное натуральное число.

Теорема 4 (Теорема о нижней оценке). Для любых натуральных k, n, s, d верно Из леммы 3 и теоремы 4 следует следующая теорема о порядке коммуникационной сложности PIR-протоколов в классе Ad.