Введение
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
