Коммуникационная сложность протоколов доступа к данным без раскрытия запроса тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В.Ломоносова

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

На правах рукописи УДК 519.712.3

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

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

01.01.09 — дискретная математика и математическая кибернетика

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

1Е1Ш1III1111111111

00Э1В6Б02 Научный руководитель

доктор физико-математических наук профессор Э.Э.Гасанов

Москва 2008

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

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

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

профессор Ложкин Сергей Андреевич

кандидат физико-математических наук Шакиров Абдыганы Абжамилович Ведущая организация: Вычислительный Центр РАН

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

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

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

А.О.Иванов

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

Актуальность темы

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

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

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

Фармацевтические базы данных. Обычно фармацевтические компании специализируются либо в изобретении новых лекарств, либо на

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

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

3В Chor, О Goldieich, Е Kushilevitz, and М 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-протоколов является построение протоколов с минимальной коммуникационной сложностью

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

4В Chor, О Goldreich, Е Kushilevitz, and М Sudan Private information retrieval In Proo of the 36th Annu IEEE Symp oil Foundations of Computer Science, pages 41-51, 1995

Рассмотрим протокол с к + 1 участником пользователем и к несообщающимися серверами (к > 1), причем каждый из серверов хранит один и тот же булев вектор х = (хд, 1) длины п — базу данных

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

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

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

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

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

Приведем формальное определение РЖ-протокола Для любого натурального п обозначим Еп = {0, ., п — 1} Пусть к, п, я, т, ,рк~г — натуральные числа, р = р° + .. + рк~1 Пусть на множестве В = {(г, г), г 6 Еп, г € Ее} задано вероятностное пространство < В, 2В,Р >, где Р(г. г) = для любых г е Е„, г € Е3 Тогда (к,п,з,т,р) РШ-протоколом называется набор из к + 2 функций I — {<3,А°, , А^-1, Д), где Я,А0,. ,А*"1,К некоторые отображения, <3 • Ек х Еп х Ее —► Ет, А1 Еп х {0,1}п -> {О, з € Ек, Я • Еп х Е$ х {0,-> {0,1}, такие,

что выполнены 2 условия

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

R(i,r,A°(Q(0,i,r),x), lA^iQik - 1,г,г),х)) = х„

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

P(Q(M,r) = g) = P(Q(i,j,r) = g).

Наиболее известные результаты по этой тематике были получены в работах С Еханина5, А Разборова и С Еханина6, Beimel, Y Ishai, Е Kushile-vitz и J F Raymond7, в О Goldreich, H karloff, L Schulman и L Trevisan 8 и в работе I Kerendis и R de Wolf9

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

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

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

5S Yekhamn New Locally Deeodable Codes and Private Information Retrieval Schemes, Electronic Colloquium on Computational Complexity (ECCC), TR06-127

•"Alexander A Razborov, Sergey Yekhamn An Omega(n1/3) Lower Bound for Bilinear Group Based Pnvate Information Retrieval FOCS 2006 739-748

7A Beimel, Y Ishai, E Kushilevitz, and J F Raymond Breaking the 0(n1f2k~1) barrier for information theoretic private information retrieval In Proc of the 43st IEEE Sym on Found of Comp Sci, 2002

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

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

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

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

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

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

Степенью существенности булевой функции f(x\, . , х{) назовем число

10О Goldreich, Н karioff, 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

nI 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

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

зд

Степенью существенности булевой вектор-функции

Е(хи ,®г) = (Л(®1>. ,Мхь ,Х1))

назовем число

5(Л = тах5(Л)

Пусть А3(д,х) = (А^д.х), Для функций

А3(д,х),А31(д,х),1 е Е^,] € Ек,д е Е8 также будем использовать следующую запись А3{д,х) — А3(д)(х),А31(д,х) = А3(д)(х), где А3(д) {0,1}" —» {0,1}^ — булева вектор-функция п переменных, А\{д) {0,1}и —+ {0,1} — булева функция п переменных

Степенью существенности функции ответов J-ro сервера А3 Е3 х {0,1}" —» {0,1 у*, ] € Е2, назовем число

Б(А3) =

Для любых г € Еп,г € Е3 определим следующую булеву функцию от р переменных • {0,1}р —> {0,1}, где Д,>г(а°, ,ак~г) =

Н(г,г,а0,. ,ак~1)

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

В работе получены следующие основные результаты

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

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

Для любого натурального й, в классе РШ-протоколов с к > 2 серверами, степень существенности функции ответов которых не превышает 4, и длина датчика случайных чисел больше длины базы данных, получена нижняя оценка коммуникационной сложности На основе нижней оценки получено точное по порядку значение коммуникационной сложности для класса РШ-протоколов со степенью существенности функции ответов 4 и достаточно большой длины датчика случайных чисел А именно, построен РШ-протокол и показано, что в данном классе РШ-протоколов его коммуникационная сложность по порядку минимальна

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

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

Апробация работы. Результаты настоящей работы докладывались на семинарах механико-математического факультета МГУ им М В Ломоносова на семинаре "Теория автоматов" под руководством академика, проф., д ф-м н В Б Кудрявцева (2005-2007 гг.), на семинаре "Вопросы сложности

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

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

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

Краткое содержание работы

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

В главе 1 исследуются границы вырожденности PIR-протоколов по основным параметрам В частности, в разделе 1 1 приводится простейший вырожденный PIR-протокол, в разделе 12 приводится простейший невырожденный PIR-протокол В разделах 13-18 приводятся доказательства утверждений о границах вырожденности PIR-протокола по основным параметрам числу серверов, по длине датчика случайных чисел, по

длине базы данных, по степени существенности функции ответов, по степени существенности реконструирующей функции

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

Теорема 1. Для любого натурального п > 12 невырожденный (k,n,s,m,p) PIR-протокол I — (Q, AQ, , Ак~г, Ft) существует тогда и только тогда, когда одновременно выполнены следующие условия

1 количество серверов к > 2,

2 длина датчика случайных чисел s > 2,

3 мощность множества запросов т> 2,

4 существует такое j € Ek, что выполнено S(AJ) > 2,

5 S(R) > 2

PIR-протоколы, для которых выполнено т = s будем обозначать четверкой параметров (k,n,s,p) Обозначим через X(ktn,s) класс всех (к,п. s,p) PIR-протоколов, где р > 0 Пусть А — некоторое множество PIR-протоколов Тогда обозначим

C(k,n,s,A) = min{C(/) I € AnX(k,n,s)}

Обозначим через Ad множество всех PIR-протоколов таких, что степень существенности функции ответов каждого сервера не превосходит d

В главе 2 исследуется коммуникационная сложность PIR-протоколов Раздел 2 1 посвящен исследованию коммуникационной сложности PIR-протоколов в классе Аъ — классе PIR-протоколов, степень существенности функции ответов которых не превосходит 2 Раздел 211 посвящен доказательству леммы о верхней оценке в данном классе, а именно в данном разделе построен PIR-протокол с заданными параметрами

Лемма 1. Для любых натуральных n, s таких что s < л/п верно

s + 1

С(2, n, s, Az) < 2] log2 —-—n + п mod s2

Назовем булеву функцией /(жг, • , щ) линейной, если для любых х\.х} G {0,1},1 <t < I верно

f(x 1, .,xt-l,xl +X%,Xt+l, ..,Xl) = f(xi, ,xt-i,x\,xt+u ,Xl) +

+ f(x 1, ,Xt-l,Xt,Xi+l, ,Xi)

Линейным (k,n,s,p) PIR-протоколом назовем такой PIR-протокол, у которого для любых j е Ek,l € € Es, г е Еп функции A]{q)

и Rt^ являются линейными функциями Положим Vг — множество всех линейных PIR-протоколов из класса Аг- Проще говоря, для любого PIR-протокола из 1>2 верно каждый бит ответа каждого сервера является суммой некоторых бит базы данных, и для того, чтобы получить значение искомого бита пользователь складывает некоторые биты ответов серверов В разделе 212 доказывается, что в классе Аг для построения PIR-протоколов можно использовать только линейные функции

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

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

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

Лемма 2. Для любых натуральных п, s таких что s <п верно

s + 1

С(2, п, s, Аг) > 2] Iog2 Будем писать а(п) = 6(1), если lim а(п) = 0, А(п) — б (В(п)), если

71—>00

А{п) — В(п) о(1) Скажем, что А(п) асимптотически не превосходит В(п) при п —> оо и обозначим А < В, если существует а(п) = о(1) такое, что начиная с некоторого номера п0, А(п) < (1 + а(п)) В{п) Если А(п) < В(п) и А(п) > В(п), то будем говорить что А ж В асимптотически равны при п —> оо и обозначать А ~ В

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

Теорема 3. Если 5 = о(л/п) при п —> оо, то при п —> оо верно

С(2,п,з,Л2) ~

и при п кратном в2 верно

С(2, п, в, Л2) = 2] 1о^2

Раздел 2 2 посвящен исследованию коммуникационной сложности РЖ-протоколов в классе Л4 — классе РЖ-протоколов, степень существенности функции ответов которых не превосходит в, В разделе 2 2 1 приводится доказательство теоремы о верхней оценке коммуникационной сложности РЖ-протоколов для к серверов, степень существенности функций ответов серверов которых не превосходит (1, где 0 < 4 < п2к~2/2к-1

Лемма 3 (Верхняя оценка). Для любых натуральных к,п и <1 таких что О < й < п2к~2/2к-1, верно

С(к,п, 2ы1/№~\ А*) < (к2 + к)41/2к~2 + 4к^

О/

В разделе 2 2 2 приводится пример РЖ-протокола при а! = з = 2? В разделе 2 2 3 приводится доказательство теоремы о нижней оценке коммуникационной сложности РШ-протоколов для к серверов, степень существенности функций ответов серверов которых не превосходит А, где й - произвольное натуральное число

Теорема 4 (Теорема о нижней оценке). Для любых натуральных к,п, в,с? верно

Т1

С (к, п, в, Аг) > к]

Из леммы 3 и теоремы 4 следует следующая теорема о порядке коммуникационной сложности РЖ-протоколов в классе Лв,

Будем писать А =4 В, если существует такая положительная константа с, что А(п) < с В(п), начиная с некоторого номера по Если А =<! В и А^ В, то будем говорить, что А и В равны по порядку при п —» оо и обозначать АжВ

Теорема 5. Если натуральные числа к,с1.п такие что (1 Ц п2к 2!2к 1 при п оо, то при п —> оо верно

С(к,п,Лс[) х § а

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

Определение 1. Для любого (к,п,з,р) РШ-протокола I — {<9, А0, .,Ак~1,Я}! будем говорить, что множество пар {(го, г0), е Еп и ответы А3{<Э{э,ът,гт),х) =

(а30т, . ,а3р)_1т)тЗ € Ек,т е Щ раскрывают базу данных х = (жо, , хп-1) е Е%, если система уравнений А](<3{],гт, гт), х) — а?1т,] е Ек,1 € Ер),т € Еъ имеет единственное решение относительно переменных 3/1, ъ £ Еп

Определение 2. Степенью раскрытия базы данных х — (жо, , хп^{) е помощью (к,п,з,р) РШ-протокола I = {Я, А0, ,Ак~1,Я) для заданной последовательности случайных чисел г = (го, ,г„_ 1) € Е™ назовем минимальное число Ь = 1(п,г), для которого существуют такая перестановка -к • Еп —> Е„, что множество пар {(7г(0),го), . , (?г(£ — 2),п_2)> и ответы

Л°(С?(0, тг(0), го), ж),. , Ак~х(${к - 1,тг(0), г0), х),.

А°(Я( 0,тг(* - 2), п-2),х), , Ак~\Я{к - 1, *■(* - 2), г*_2), ж)

не раскрывают базу данных, а множество пар {(7т(0),Го), , (7г(<—1),г4_1)} и ответы

А°(д{0,1г(0),го),х)> .,А*-1(С}{к- 1,тг(0), го), х),

,А°(д(0,я-с* -1),п_х),ж),. .,Ак-\Я{к ~ 1,тг(£ - 1),г«_0,

раскрывают базу данных х

Обозначим

t{ri) = max£(n,f), t{n) = mmi(n,f)

r€E?

В разделе 3 2 рассматривается протокол I1/3 для 2-х серверов, описанный в работе В Chor, О Goldreich, Е Kushilevitz и М Sudan12 Приводится доказательство следующей теоремы.

Теорема 6. Для любого натурального п, такого что |п1//3 - целое, для (2,n,s,p) PIR-протокола I1/3 = (Q, А0, А1, Д) верно

\n2'z <t_(En) <t(En) -2.

В разделе 3 3 рассматривается протокол Р°1 для к серверов, описанный в работе A Beimel, Y Ishai и Е Kushilevitz13 Приводится доказательство следующей теоремы

Теорема Т. Для (2,n,s,p) PIR-протокола P°l = {Q,Aa,Al,R) верно

где т такое что С^ > п

В разделе 3.4 рассматривается протокол /2 для 2-х серверов, описанный в работе Майлыбаевой Г А 14 Приводится доказательство следующей теоремы

Теорема 8. Для (2,n, s,p) PIR-протокола I2 = (Q, A1, R) верно

t{n) = t(n) = s

12В Chor, О Goldreich, Е Kushilevitz, and M Sudan Private information retrieval In Proc of the 36th Annu IEEE Symp on Foundations of Computer Science, pages 41-51, 1995

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

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

В разделе 3 5 рассматривается протокол Id для 2-х серверов, с мощностью датчика случайных чисел равной s, принадлежащий классу Aiog.lS, описанный в в работе Майлыбаевой Г А15 Приводится доказательство следующей теоремы

Теорема 9. Для (2,n,s,p) PIR-протокола Id ~ (Q,A°,Al,R) верно

^==£(n)<i(n) = log2s

В разделе 3 5 рассматривается протокол Idl для 2-х серверов из класса Ad, где 0 < d < п2/3 - произвольное натуральное число, описанный в работе Майлыбаевой Г.А 15 Приводится доказательство следующей теоремы

Теорема 10. Для (2,n,s,p) PIR-протокола Idl = {Q,А0,А1,/?} верно

1 _1 -d = t(n) < t(n) = -d-2

Благодарности.

Я благодарю научного руководителя доктора физико-математических наук, профессора Гасанова Эльяра Эльдаровича за постановку задачи, постоянное внимание и помощь в работе, а также академика, доктора физико-математических наук Кудрявцева Валерия Борисовича за многочисленные полезные советы на всех этапах подготовки диссертации Я выражаю благодарность коллективу кафедры МаТИС за теплую творческую атмосферу

Работы автора по теме диссертации

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

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

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

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

4 Guiñara A Maylybaeva, Communication complexity for a special class of private information retrieval protocols, In proc of ICM2006, August (2006), pp 499

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

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

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

Издательство ЦПИ при механико-математическом факультете МГУ им М В Ломоносова

Подписано в печать №,03 ОЗ Формат 60x90 1/16 Уел печ л /.<?5 Тираж 150 экз Заказ Н

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета

1 |i 11 >

Введение1 1 '

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

1.1 Простейший вырожденный PIR-протокол.

1.2 Простейший невырожденный PIR-протокол.

1.3 Граница вырожденности по числу серверов.

1.4 Граница вырожденности по длине запроса.

1.5 Граница вырожденности по мощности множества значений датчика случайных чисел.

1.6 Граница вырожденности по длине базы данных.

1.7 Граница вырожденности по функции ответов.

1.8 Граница вырожденности по реконструирующей функции

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

2.1 Коммуникационная сложность PIR-протоколов в классе Ai- ■

2.1.1 Верхняя оценка коммуникационной сложности в классе А2.

2.1.2 Сведение к линейным PIR-протоколам.

2.1.3 Пример PIR-протокола при s — 2.

2.1.4 Пример PIR-протокола при s — 3.

2.1.5 Нижняя оценка коммуникационной сложности в классе

2.2 Коммуникационная сложность PIR-протоколов в классе Аа

2.2.1 Верхняя оценка коммуникационной сложности в классе Ad.

2.2.2 Пример PIR-протокола при d = s = 2?.

2.2.3 Нижняя оценка коммуникационной сложности в классе

3 Степень раскрытия PIR-протоколов

3.1 Степень раскрытия PIR-протоколов.

3.2 Степень раскрытия протокола с коммуникационной сложностью 0(п1/3).

3.3 Степень раскрытия протокола 1ро1.

3.4 Степень раскрытия протокола из Ач.

3.5 Степень раскрытия протоколов из Ла.

В связи с постоянным расширением области применения компьютерных технологий, одним из актуальных направлений дискретной математики и математической кибернетики являются операции хранения и поиска информации. В последние десятилетия активно развивается новое научное направление, связанное с оптимальным хранением и поиском информации, именуемое теорией информационного поиска. Одним из главных носителей этого направления является теория баз данных [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 889894, 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-21851, 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, 98110.

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-протоколов. Дискретная математика.