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

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Майлыбаева Гульнара Абаевна. Коммуникационная сложность протоколов доступа к данным без раскрытия запроса : диссертация ... кандидата физико-математических наук : 01.01.09 / Майлыбаева Гульнара Абаевна; [Место защиты: Московский государственный университет].- Москва, 2007.- 121 с.: ил. РГБ ОД, 61 08-1/359

Содержание к диссертации

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.2 Пример PIR-протокола при d = |,s = 2» 76

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

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

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

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

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

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

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

Список литературы 93

Приложение 1 98

Простейший невырожденный PIR-протокол
Граница вырожденности по длине базы данных
Верхняя оценка коммуникационной сложности в классе Л2
Степень раскрытия протокола с коммуникационной сложностью 0(^/3)

Введение к работе

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

і не стал известен ни одному из серверов. Протокол состоит из следующих шагов.

Пользователь имеет номер бита г и вырабатывает случайное число г. По числам і иг пользователь вычисляет с помощью специальной функции, называемой функцией запросов, к чисел д-⁷ и посылает j-му серверу запрос
Каждый из к серверов по полученному запросу qi и базе данных х с помощью специальной функции ответов вычисляет вектор о? и посылает его пользователю.
Пользователь по числам і, г ж к ответам серверов а-⁷ вычисляет с помощью реконструирующей функции нужный битжі.

Первое требование к протоколу состоит в том, что ни один из серверов по своему запросу д-⁷ не может понять, с помощью какого бита г этот запрос был порожден. Это требование называется требованием защищенности. Второе требование к протоколу, называемое требованием корректности, заключается в том, что пользователь по ответам серверов правильно восстанавливает бит Х{. Предполагается, что всем участникам протокола — и пользователю и серверам — известны функции запросов, ответов и реконструирующая. Но серверам не известно случайное число г и, разумеется, не известен номер бита г. Целью построения 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-протоколов с более чем 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}. Пусть к, п, s, 771, р,... ,p^fc-1 — натуральные числа, р = р + ... + р^к~^г. Пусть на множестве В — {(г, г), і Є Е_п, г Є E_s] задано вероятностное пространство < В,2^В,Р >, где Р(г,г) = ^, для любых і Є Е_п: г Є E_s. Тогда (k,n,s,m,p) PIR-протоколом называется набор из k + 2 функций / = (Q, А⁰,..., A^k~^l, R), где Q, A⁰,..., A^k~^l, R некоторые отображения, Q : Е_к х Е_п х Е_я -> Е_т, А* : Е_т х {0,1}^п -> {0,1}^, j Є Е_к,

R: E_n x E_s x {0,1}^P —» {0,1}, такие, что выполнено 2 условия:

корректности: для любых і Є Е_п, г Є E_s выполнено

R{i,r,A⁰(Q(0,i,r),x),...,A^k-^l{Q{k-l,i,r)_:x)) = x_i;

защищенности: для любых q Є Е_т, t Є Ek, і, j Є Е_п выполнено

P(Q(t,i,r) = q) = P(Q(t,j,r) = q).

Здесь и везде далее /с — число серверов; п — длина базы данных х = (xq,x\, ..., ж„_і); s — параметр датчика случайных чисел, точнее датчик случайных чисел дает равновероятно числа из множества-Е¹,,; т — характеристика функции запросов Q, точнее функция запросов Q принимает значения из Е_т] pi — количество бит в ответе j-ro сервера, А> — функция ответа j-ro сервера (j Є Ek); R — реконструирующая функция.

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

Пользователь, имея запрос г, вырабатывает случайное число г Є E_s, для каждого j Є Ek вычисляет qi = Q(j,i,r) и посылает g^J серверу Sj.

Каждый сервер Sj, j Є Ek, вычисляет а-⁷ = (а^,..., а.^₇_₁) = A^J(qi,x) и посылает вектор о? пользователю.

Пользователь вычисляет Х{ — R(i, г, а⁰,..., а^к~¹).

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

Величина C(I) = к) log₂ т[-\-р называется коммуникационной сложностью протокола I, и представляет собой число бит, переданных в процессе протокола.

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

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

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

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

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

Пользователь желает узнать значение г-го бита хг этого вектора так, чтобы номер бита і не стал известен ни одному из серверов. Протокол состоит из следующих шагов. 1) Пользователь имеет номер бита г и вырабатывает случайное число г. По числам і иг пользователь вычисляет с помощью специальной функции, называемой функцией запросов, к чисел д-7 и посылает j-му серверу запрос 2) Каждый из к серверов по полученному запросу qi и базе данных х с помощью специальной функции ответов вычисляет вектор о? и посылает его пользователю. 3) Пользователь по числам і, г ж к ответам серверов а-7 вычисляет с помощью реконструирующей функции нужный битжі. Первое требование к протоколу состоит в том, что ни один из серверов по своему запросу д-7 не может понять, с помощью какого бита г этот запрос был порожден. Это требование называется требованием защищенности. Второе требование к протоколу, называемое требованием корректности, заключается в том, что пользователь по ответам серверов правильно восстанавливает бит Х{. Предполагается, что всем участникам протокола — и пользователю и серверам — известны функции запросов, ответов и реконструирующая. Но серверам не известно случайное число г и, разумеется, не известен номер бита г. Целью построения PIR-протоколов является построение протокола с минимальной коммуникационной сложностью для заданных пик.

Известно, что всегда существует простейший 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-протоколов.

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

Допустим, некоторый пользователь базы данных хочет узнать запись этой базы данных таким образом, чтобы администратор базы данных ничего не узнал о том, что интересует пользователя. Для решения этой задачи пользователь может купить всю базу данных и выделить из нее нужную ему информацию. Тогда администратор точно ничего не узнает об интересах пользователя, а именно, не узнает номер записи которую хотел узнать пользователь. Однако, если мы будем учитывать, что за каждую запись базы данных пользователь должен заплатить некоторую сумму, покупка всей базы данных обойдется ему очень дорого. К тому же, если база данных хранится на сервере, к которому есть доступ через общедоступную сеть, например, Интернет, тогда, чтобы скачать всю базу данных, пользователю потребуется очень много времени. Чтобы решить эту проблему, пользователь приходит к математику. Математик дает пользователю 3 алгоритма (программы): алгоритм запросов, алгоритм ответов, и реконструирующий алгоритм, которые представляют собой необходимые алгоритмы для проведения PIR-протокола. Пользователь приходит в компанию, которая предоставляет доступ к базе данных, и предлагает заплатить за необходимое количество информации, которую он скачает из базы данных, но при условии, что сервер для выработки ответа на запрос пользователя будет пользоваться определенным алгоритмом. А именно, одним из алгоритмов, который математик предоставил пользователю, алгоритмом ответов. Будем считать, что каждая запись базы данных - один бит и пользователь хочет узнать значение одного бита базы данных. Тогда пользователь обязуется заплатить за каждый бит информации, которую скачает с сервера. С такой же просьбой пользователь приходит в другую компанию, которая предоставляет доступ к аналогичной базе данных. Компании выгодно иметь такой сервис, поскольку в этом случае пользователь платит не за один бит информации, которую он хочет узнать, а за количество бит, которое содержится в ответе сервера. Пользователю выгодно использовать PIR-протокол, поскольку в этом случае ему надо будет заплатить за гораздо меньшее количество бит, чем в случае покупки всей базы данных и при этом его интересы останутся тайной для всех, кроме него самого. Например, в лучшем PIR-протоколе для 2-х серверов, длина ответа каждого из серверов по порядку равна п1 3, где п длина базы данных. Для того, чтобы получить желаемую информацию из базы данных, пользователь вырабатывает запросы к серверам, используя алгоритм запросов и генератор случайных чисел. Каждый из запросов он передает соответствующему серверу. Сервер, используя алгоритм, который ему предоставил пользователь, вычисляет ответ и передает его пользователю. Наконец, используя последний, реконструирующий алгоритм, пользователь получает информацию, которая его интересовала. Поскольку используемые алгоритмы удовлетворяют свойству корректности, пользователь всегда получит желаемую информацию. А свойство защищенности гарантирует, что администраторы серверов по запросу пользователя ничего не узнают о полученной информации.

Данный раздел носит обзорный характер. В русскоязычной литературе такой обзор не публиковался. В англоязычной литературе были опубликованы следующие обзоры по PIR-протоколам: [2, D. Asonov, 2001 г.],[18, W. Gasarch, 2004 г.]. На настоящий момент в области PIR-протоколов известны следующие результаты. В [27, Sergey Yekhanin, 2006 г.] был получен PIR-протокол для к = 3 серверов с коммуникационной сложностью 0(п10 ). На данный момент, коммуникационная сложность этого протокола является наилучшей для к = 3. В [6, A.Beimel, Y.Ishai, E.Kushilevitz, J.-F.Raymond, 2002 г.] для каждого натурального к 2 получен PIR-протокол с коммуникационной СЛОЖРГО-стью nO( gk/kigk) для _ 2 сложность построенного PIR-протокола равна 0(п1 ). На данный момент, коммуникационная сложность этого протокола является наилучшей для к = 2. В [20, O.Goldreich, H.Karloff, L.Schulman, L.Trevisan, 2002 г.] было показано, что если функции ответов всех серверов линейные, и количество бит в ответе любого сервера равно а, то длина запроса должна быть не меньше О(трг). Также было показано, что сложность любого PIR-протокола для 2-х серверов, функции ответов которого являются линейными, и пользователь использует ровно а бит из ответа каждого сервера, не превышает 0(nlla+l). Для доказательства нижних оценок авторы преобразовывают произвольный PIR-протокол в LDC(Locally Decodable Code) протокол и приводят доказательство оценки для LDC-протокола. В [13, В. Chor, О. Goldreich, Е. Kushilevitz, М. Sudan, 1998 г.] была получена следующая нижняя оценка. Если функция запросов линейна и ответ любого сервера это ровно один бит, тогда длина запроса к каждому серверу должна быть не меньше п — 1 бит. Эта оценка является точной. В той же работе построен PIR-протокол с такой же коммуникационной сложностью.

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

В [24, I.Kerendis и R. de Wolf, 2003 г.] было показано, что если пользователь использует из ответа каждого сервера не более а бит, то длина запроса должна быть не меньше (трп). Для доказательства нижней оценки авторы преобразовывают произвольный PIR-протокол в квантовый PIR-протокол и приводят доказательство оценки для квантового PIR-протокола.

В [10, R.Beigel, L.Fortnow, W.Gasarch, 2003 г.] было показано, что если каждый сервер посылает в ответ пользователю ровно один бит, то количество бит в запросе должна быть не менее п — 2. При этом существует PIR-протокол, описанный в [13, В. Chor, О. Goldreich, Е. Kushilevitz, М. Sudan, 1998 г.], где пользователь посылает каждому серверу п — 1 бит и получает в ответ ровно 1 бит от каждого сервера.

Покрывающие коды. Опишем метод, основанный на покрывающих кодах (covering codes), предложенный в [19, Y. Gertner, Y. Ishai, Е. Kushilevitz, and Т. Malkin, 1998 г.], который позволяет уменьшить количество серверов, участвующих в описанном выше протоколе. Начнем с примера для d = 3. В этом случае в протоколе участвуют 2d = 8 серверов, каждому из которых поставлен в соответствие двоичный вектор длины 3. База данных представляется как трехмерный куб со сторонами длины m = п1//3. Каждому серверу Sj,j Є Е$ пользователь посылает подкуб булева кубаЕ , определенный подмножествами AQ0, А11, Аа22 С Ет, сервер Sj отвечает суммой по модулю 2 всех бит, содержащимися в этом подкубе. Определение 4. Покрывающим кодом с радиусом 1 в множестве {0, l}d назовем подмножество точек этого лтожества Cd = {CQ, СІ, ..., Q_i} С {О, l}d такое, что {0,1} С (J B(CJ,1), где В(с, 1) это множество d битовых векторов, которые отличаются от вектора с ровно в одной позиции.

Имея покрывающий код Cd = {CQ, ..., Ck-i} для {0, l}d, можно использовать метод эмуляции для получения протокола для к серверов с коммуникационной сложностью 0{nlfd). База данных прелставляется как множество точек из F Пользователь, который хочет узнать значение бита с индексом і = (г о,... ,id-i), выбирает d случайных подмножеств А, А,..., Аа_г С Eni/d, вычисляет А\ = АІ ф г0,.. , А\_х = AQd_x ф id-i С Eni/d и посылает серверу Sj,j Є Ек множества, соответствующие кодовому слову Cj Є Cd- Каждый сервер Sj отвечает на свой запрос и эмулирует ответы тех серверов, которые ассоциированы с кодовыми словами, которые покрываются словом Cj, всего nl d ответов. Таким образом, ответы к серверов позволяют пользователю вычислить желаемый бит, как если бы он получил ответы от 2d серверов.

Подсчитаем коммуникационную сложность протокола. Пользователь посылает d-n1 d бит каждому серверу, общее количество бит, полученное пользователем в ответ от всех серверов равно k+(2d — k)nl/d. В итоге получаем C(I ) = (dk 2d — k)nlld + к в случае протокола для к серверов.

Подсчитаем количество переданных бит. Количество бит, переданных пользователем серверам, равно 2(2к - \)т = (2к - І)?!1/2 -1. Пользователь передает 2к — 1 множество AJQ,... ,А2к_2 серверу Sj,j = 0,1. Количество бит, переданных пользователю первым сервером, равно количеству комбинаций всевозможных множеств А0:..., А2к_2 и равно (2к — 1)т+ 1 = (2к — l)n1//2/c_1 + 1. Количество бит, переданных пользователю вторым сервером, равно количеству комбинаций всевозможных множеств А 0,..., А 2к_2 и равно (22 1 - 2к)т2к-3 = (22к 1 - 2к)п(2к- 2к-1). Из ответа второго сервера пользователю необходимо знать ровно 22fc_1 — Ik бит, причем позиции этих бит в ответе второго сервера не зависят от значения бит базы данных. Тогда мы можем скомбинировать описанный протокол и протокол для к — 1 сервера методом, описанным в начале главы.

Подсчитаем коммуникационную сложность результирующего протокола. Коммуникационная сложность протокола для к — 1 сервера для базы данных длины Oin "3 "1 ) равна 0(nly/2fc_1). Количество бит, которое пользователь хочет узнать из ответа второго сервера с помощью эмуляции протокола для к — 1 сервера равно константе 22fc_1 — 2к. Количество бит, переданных первым сервером и пользователем на первом шаге протокола для 2-х серверов, остается прежним. Получаем, что сложность результирующего протокола для к серверов равна 0{п1/2к 1).

Общий метод построения PIR-протоколов для к серверов. В работе [7, A.Beimel, Y.Ishai and E.Kushilevitz and E.Kushilevitz, 2003 г.] был предложен общий метод построения PIR-протоколов. База данных х длины п представляется, как многочлен рх{Уо, j m-i) от т переменных, степени d, YQ,. .. ,Ут_і Є {0,1}. Степень многочлена d и число переменных га выбирается так что md п. Многочлен представляет базу данных в следующем смысле: каждому индексу г Є Еп ставится в соответствие вектор Е(г) Є {0,1}т, такой, что для любого і є Еп верно рх(Е(г)) = Х{. Отображение Е : Еп —»Є {0,1}т также называется кодированием. Значения многочлена рх(Уо, , Ущ-і) Для векторов другого вида не важны.

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

Рассмотрим некоторое обобщение PIR-протоколов на случай, когда несколько серверов могут объединяться, обмениваться полученной от пользователя информацией. В случае, когда не более, чем t,l t к могут объединиться, говорят о -защищенном PIR-протоколе. Такие протоколы были рассмотрены, в том числе, в работе [9, C.Blundo, P.D Arco and A. De Santis, 2002 г.].

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

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

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

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

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

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