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

• Автор: Майлыбаева, Гульнара Абаевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 121 с.

Оглавление
< I I 1 1 '
Введение1
1 Границы вырожденности протоколов доступа к данным без раскрытия запроса
1.1 Простейший вырожденный РШ-протокол
1.2 Простейший невырожденный РЩ-протокол
1.3 Граница вырожденности по числу серверов
1.4 Граница вырожденности по длине запроса
1.5 Граница вырожденности по мощности множества значений
датчика случайных чисел
1.6 Граница вырожденности по длине базы данных
1.7 Граница вырожденности по функции ответов
1.8 Граница вырожденности по реконструирующей функции
2 Коммуникационная сложность РШ-протоколов
2.1 Коммуникационная сложность РШ-протоколов в классе Ач-
2.1.1 Верхняя оценка коммуникационной сложности в классе А2
2.1.2 Сведение к линейным РШ-протоколам
2.1.3 Пример РШ-протокола при з
2.1.4 Пример РЩ-протокола при й
2.1.5 Нижняя оценка коммуникационной сложности в классе

2.2 Коммуникационная сложность РШ-протоколов в классе Л
2.2.1 Верхняя оценка коммуникационной сложности в классе Дг
2.2.2 Пример РПГ-протокола при с1 = з = 2§

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

3 Степень раскрытия РШ-протоколов
3.1 Степень раскрытия РЩ-протоколов
3.2 Степень раскрытия протокола с коммуникационной сложностью 0{п113)
3.3 Степень раскрытия протокола 1рЫ
3.4 Степень раскрытия протокола из А2
3.5 Степень раскрытия протоколов из Ал
Список литературы
Приложение

Введение
В связи с постоянным расширением области применения компьютерных технологий, одним из актуальных направлений дискретной математики и математической кибернетики являются операции хранения и поиска информации. В последние десятилетия активно развивается новое научное направление, связанное с оптимальным хранением и поиском информации, именуемое теорией информационного поиска. Одним из главных носителей этого направления является теория баз данных [28, Э.Э.Гасанов, 1985 г.],[29,
Э.Э.Гасанов, В.Б. Кудрявцев, 2002 г.]. В данной работе рассматривается одна из составляющих данной теории - проблема защищенности баз данных и поисковых систем, а именно проблема защиты информации в интересах пользователей.
В настоящее время знание некоторых предпочтений пользователей приобретает известное значение и цену. С другой стороны, нет никаких оснований считать, что администратор сервера, на котором хранится база данных, не использует информацию о своем пользователе против его самого.
Протоколы извлечения информации без раскрытия запроса позволяют пользователю получить желаемый бит информации из базы данных таким образом, что администратор базы данных ничего не узнает о номере бита, который запрашивал пользователь. Понятие такого протокола впервые было введено в работе [12, В. Chor, О. Goldreich, E. Kushilevitz, М. Sudan, 1995 г.] под названием Private Information Retrieval, поэтому мы в дальнейшем будем называть такие протоколы PIR-протоколами.
Существует множество примеров, где использование протоколов, которые скрывают от администраторов базы данных интересы их пользователей (PIR-протоколов), может быть полезно.
Фармацевтические базы данных. Обычно фармацевтические компании специализируются либо в изобретении новых лекарств, либо на

тогда положим

ао,о
ы0,ш
О'п—1
П—1,771—1 J
Є M(m, п).
Для вычисления ответа сервер Sj. j 6 Е2 использует матрицы BJ0,B{, которые будут описаны ниже, причем В°,В° е М(Г + l",n), a Bq,B G М(21п). Полагаем, что пользователь знает вид всех этих матриц.
Сервер Sj вычисляет ответ а3 используя формулу а3 = A3(q3,x) = (Вхт)т и посылает результат пользователю.
Пусть Е — единичная матрица из О — нулевая матрица из
т.е.

V о о

V о о

Если I" 0, то пусть Е' — единичная матрица их О' — нулевая
матрица из М(1',1"), О” — нулевая матрица из
Тогда матрицы используемые первым сервером So имеют следующий вид:

Е О О Е О' О" О" О" О" Е'
О Е Е О О’ О" О" О" О" Е'
матрицы используемые вторым сервером S имеют следующий вид:

О Е О О О'

Е О О О О' О О Е О О'
ч О О О Е О1
Шаг 3. Пользователь действует по следующей схеме.
1. Если д0 = г = 0, то
(а) если г < 21', то д1 — 0 и
1. если г < I', то XI получается как сумма двух бит из ответов обоих серверов, а именно = а® +