Получение частной информации

редактировать

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

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

Проблема была представлена в 1995 году Чором, Голдрайхом, Кушилевицем и Суданом в теоретико-информационной постановке и в 1997 году Кушилевицем и Островским в вычислительной постановке. С тех пор были обнаружены очень эффективные решения. Единая база данных (вычислительно частная) PIR может быть достигнута с постоянной (амортизированной) связью, а k-база данных (теоретическая информация) PIR может быть выполнена с $n O (log ⁡ log ⁡ kk log ⁡ k) {\ displaystyle n ^ { O \ left ({\ frac {\ log \ log k} {k \ log k}} \ right)}}$ ${\ displaystyle n ^ {O \ left ({\ frac {\ log \ log k} {k \ log k}} \ right)}}$ связь.

Содержание

1 Достижения в вычислительной PIR
2 Достижения в области теории информации PIR
3 Отношение к другим криптографическим примитивам
4 Варианты PIR
5 Реализации PIR
- 5.1 Примечания
6 См. Также
7 Ссылки
8 Внешние ссылки

Достижения в вычислительной PIR

Первая вычислительная схема PIR с одной базой данных для достижения сложности связи менее $n {\ displaystyle n}$ $n$ был создан в 1997 году Кушилевицем и Островским и достиг коммуникативной сложности $n ϵ {\ displaystyle n ^ {\ epsilon}}$ $n ^ {\ epsilon}$ для любого $ϵ {\ displaystyle \ epsilon}$ $\ e psilon$ , где $n {\ displaystyle n}$ $n$ - количество бит в базе данных. Безопасность их схемы была основана на хорошо изученной задаче квадратичной остаточности. В 1999 году Кристиан Качин, Сильвио Микали и Маркус Стадлер достигли полилогарифмической сложности общения. Безопасность их системы основана на предположении сокрытия фи. В 2004 году достигнута логарифмическая сложность связи $O (ℓ log ⁡ n + k log 2 ⁡ n) {\ displaystyle O (\ ell \ log n + k \ log ^ {2} n)}$ $O (\ ell \ log n + k \ log ^ {2} n)$ , где $ℓ {\ displaystyle \ ell}$ $\ ell$ - длина строк, а $k {\ displaystyle k}$ $k$ - параметр безопасности. Безопасность его системы сводится к семантической безопасности гибкой по длине аддитивно гомоморфной криптосистемы, такой как криптосистема Дамгарда – Юрика. В 2005 году Крейг Джентри и достиг логарифмической сложности связи, которая извлекает лог-квадрат (последовательные) биты из базы данных. Безопасность их схемы также основана на варианте предположения о сокрытии фи. В конце концов, в 2015 году скорость связи снизилась до $1 {\ displaystyle 1}$ $1$ .

Все предыдущие вычислительные протоколы PIR сублинейной связи требовали линейной вычислительной сложности $Ω (n) {\ displaystyle \ Omega (n)}$ $\ Omega (n)$ операций с открытым ключом. В 2009 году разработан вычислительный протокол PIR со сложностью связи $O (ℓ log ⁡ n + k log 2 ⁡ n) {\ displaystyle O (\ ell \ log n + k \ log ^ {2} n)}$ $O (\ ell \ log n + k \ log ^ {2} n)$ и вычисление в наихудшем случае $O (n / log ⁡ n) {\ displaystyle O (n / \ log n)}$ $O (n / \ log n)$ операций с открытым ключом. Методы амортизации, которые извлекают непоследовательные биты, были рассмотрены Рафаилом Островским и Амитом Сахаи.

. Как показали Островский и Скейт, схемы Кушилевица и Островского и Липмаа используют аналогичные идеи, основанные на гомоморфное шифрование. Протокол Кушилевица и Островского основан на криптосистеме Голдвассера-Микали, тогда как протокол Липмаа основан на криптосистеме Дамгарда-Юрика.

Достижения в теоретической информации PIR

Достижение Информационная безопасность требует предположения, что существует несколько несовместимых серверов, каждый из которых имеет копию базы данных. Без этого предположения любой теоретически безопасный протокол PIR требует объема обмена данными, который по крайней мере равен размеру базы данных n. Многосерверные протоколы PIR, устойчивые к неотвечающим или злонамеренным / вступающим в сговор серверам, называются надежными или византийскими надежными соответственно. Эти вопросы впервые были рассмотрены Беймелем и Шталом (2002). ℓ-серверная система, которая может работать там, где отвечают только k серверов, ν серверов отвечают неправильно, и которая может противостоять до t серверов в сговоре без раскрытия запроса клиента, называется «t-private ν-византийский надежный k-out -оф-ℓ ПИР »[DGH 2012]. В 2012 г. К. Девет, И. Гольдберг и Н. Хенингер (DGH 2012) предложил оптимально устойчивую схему, которая является устойчивой к Византии до $ν < k − t − 1 {\displaystyle \nu$ $\ nu <kt-1$ , что является теоретическим максимальным значением. Он основан на более раннем протоколе Голдберга, который использует секретное использование Шамира, чтобы скрыть запрос. Голдберг выпустил реализацию C ++ на Sourceforge.

Связь с другими криптографическими примитивами

Односторонние функции необходимы, но недостаточно известны для нетривиальных (т. Е. с сублинейной связью) поиск частной информации из единой базы данных. Фактически, такой протокол был доказан и Рафаилом Островским как подразумевающий передачу без внимания (см. Ниже).

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

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

Варианты PIR

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

Протокол CPIR (Computationally Private Information Retrieval) аналогичен протоколу PIR: получатель извлекает выбранный им элемент из базы данных отправителя, так что отправитель не знает, какой элемент был передан. Единственное отличие состоит в том, что конфиденциальность защищена от полиномиально ограниченного отправителя.

Протокол CSPIR (вычислительно-симметричный поиск частной информации) используется в аналогичном сценарии, в котором используется протокол CPIR. Если отправитель владеет базой данных, а получатель хочет получить i-е значение в этой базе данных, в конце выполнения протокола SPIR получатель не должен был ничего узнавать о значениях в базе данных, кроме i-го. один.

Реализации PIR

В литературе были реализованы многочисленные вычислительные схемы PIR и теоретико-информационные PIR. Вот неполный список:

Percy ++ включает реализации [AG 2007, DGH 2012, CGKS 1998, Goldberg 2007, HOG 2011, LG 2015].
Popcorn - это реализация PIR, адаптированная для медиа [GCMSAW 2016 ].
RAID-PIR - это реализация схемы ITPIR [DHS 2014].
SealPIR - это быстрая реализация CPIR [ACLS 2018].
upPIR - это Реализация ITPIR [Cappos 2013].
XPIR - это быстрая реализация CPIR [ABFK 2014].

Примечания

См. Также

Ссылки

Внешние ссылки