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

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

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

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

Достижения в области вычислительных PIR

Первая вычислительная PIR-схема с одной базой данных, обеспечивающая сложность связи менее $n$ был создан в 1997 году Кушилевицем и Островским. ^[3] и достигли коммуникационной сложности $n^{\epsilon }$ для любого $\epsilon$ , где $n$ количество битов в базе данных. Безопасность их схемы основывалась на хорошо изученной проблеме квадратичной невязки . В 1999 году Кристиан Кашен, Сильвио Микали и Маркус Стадлер. ^[4] достигнута полилогарифмическая сложность связи. Безопасность их системы основана на предположении о сокрытии Фи . В 2004 году Хельгер Липмаа ^[5] достигнута логарифмическая сложность связи $O(\ell \log n+k\log ^{2}n)$ , где $\ell$ длина строк и $k$ является параметром безопасности. Безопасность его системы сводится к семантической безопасности гибкой по длине аддитивно гомоморфной криптосистемы, такой как криптосистема Дамгорда-Юрика . В 2005 году Крейг Джентри и Зульфикар Рамзан ^[6] достигнута логарифмическая сложность связи, которая извлекает логарифмические (последовательные) биты базы данных. Безопасность их схемы также основана на варианте предположения о сокрытии Фи. Скорость связи наконец снизилась до $1$ Авторы: Аггелос Киайяс , Никос Леонардос , Хельгер Липмаа , Катерина Павлик , Цян Тан , в 2015 году. ^[7]

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

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

Достижения в области теории информации PIR

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

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

Односторонние функции необходимы, но не являются достаточными для нетривиального (т. е. с сублинейной связью) поиска конфиденциальной вычислительной информации из одной базы данных. доказали, что такой протокол Фактически, Джованни Ди Крещенцо , Тал Малкин и Рафаил Островский подразумевает передачу по невнимательности (см. ниже). ^[12]

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

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

Варианты ПИР

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

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

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

PIR-реализации

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

МачПИР ^[15] — это реализация CPIR как расширение Postgres C/C++ [GitHub, 2021].
ПечатьПИР ^[16] — это быстрая реализация CPIR [ACLS 2018].
Попкорн ^[17] — это реализация PIR, адаптированная для средств массовой информации [GCMSAW 2016].
Перси++ ^[11] включает реализации [AG 2007, DGH 2012, CGKS 1998, Goldberg 2007, HOG 2011, LG 2015].
РЕЙД-ПИР ^[18] является реализацией схемы ITPIR [DHS 2014].
XPIR ^[19] представляет собой быструю реализацию CPIR [ABFK 2014].
вверхPIR ^[20] является реализацией ITPIR [Cappos 2013].

Примечания

^ Баумелер, Эмин; Бродбент, Энн (17 апреля 2014 г.). «Квантовый поиск частной информации имеет линейную коммуникационную сложность». Журнал криптологии . 28 : 161–175. arXiv : 1304.5490 . дои : 10.1007/s00145-014-9180-2 . S2CID 1450526 .
^ Перейти обратно: ^а ^б Чор, Бенни ; Кушилевиц, Эяль; Гольдрейх, Одед; Судан, Мадху (1 ноября 1998 г.). «Поиск частной информации» (PDF) . Журнал АКМ . 45 (6): 965–981. CiteSeerX 10.1.1.51.3663 . дои : 10.1145/293347.293350 . S2CID 544823 .
^ Перейти обратно: ^а ^б ^с Кушилевиц, Эяль; Островский, Рафаил (1997). «Репликация не нужна: единая база данных, получение конфиденциальной информации». Материалы 38-го ежегодного симпозиума по основам информатики . Майами-Бич, Флорида, США: Компьютерное общество IEEE. стр. 364–373. CiteSeerX 10.1.1.56.2667 . дои : 10.1109/SFCS.1997.646125 . ISBN 978-0-8186-8197-4 . S2CID 11000506 .
^ Кашен, Кристиан; Микали, Сильвио; Стадлер, Маркус (1999). «Вычислительный поиск конфиденциальной информации с помощью полилогарифмической связи». Достижения в криптологии – EUROCRYPT '99 . Прага, Чехия: Springer-Verlag. стр. 402–414. дои : 10.1007/3-540-48910-X_28 . ISBN 978-3-540-48910-8 .
^ Перейти обратно: ^а ^б Липмаа, Хельгер (2005). «Забывчивый протокол передачи с логарифмической связью». Материалы 8-й Международной конференции по информационной безопасности (ISC 2005) . Конспекты лекций по информатике. Том. 3650. Сингапур: Springer-Verlag. стр. 314–328. CiteSeerX 10.1.1.73.8768 . дои : 10.1007/11556992_23 . ISBN 978-3-540-31930-6 .
^ Джентри, Крейг; Рамзан, Зульфикар (2005). «Поиск частной информации из одной базы данных с постоянной скоростью передачи данных». ИКАЛП . ЛНКС. Том. 3580. Спрингер. стр. 803–815. CiteSeerX 10.1.1.113.6572 . дои : 10.1007/11523468_65 .
^ Киайас, Аггелос; Леонардос, Никос; Липмаа, Хельгер; Павлик, Катерина; Тан, Цян (2015). «Оптимальная скорость получения частной информации с помощью гомоморфного шифрования». Труды по технологиям повышения конфиденциальности 2015 . Том. 2015. ДЕ ГРУЙТЕР. стр. 222–243. дои : 10.1515/popets-2015-0016 . hdl : 20.500.11820/0f84afcb-8ee1-4744-a2ba-4642104c51c5 .
^ Перейти обратно: ^а ^б Липмаа, Хельгер (2010). «Первый протокол CPIR с вычислениями, зависящими от данных». Материалы 12-й Международной конференции по информационной безопасности и криптологии . Конспекты лекций по информатике. Том. 5984. Сеул, Корея: Springer-Verlag. стр. 193–210. CiteSeerX 10.1.1.215.7768 . дои : 10.1007/978-3-642-14423-3_14 . ISBN 978-3-642-14423-3 .
^ Ишаи, Юваль; Кушилевиц, Эяль; Островский, Рафаил; Сахай, Амит (2004). «Батч-коды и их применение» (PDF) . СТОК'04 . АКМ. стр. 262–271. дои : 10.1145/1007352.1007396 . Проверено 23 октября 2015 г.
^ Островский, Рафаил; Скейт III; Уильям Э. (2007). «Обзор поиска частной информации из одной базы данных: методы и приложения». Материалы 10-й Международной конференции по практике и теории криптографии с открытым ключом . Спрингер-Верлаг. стр. 393–411. дои : 10.1007/978-3-540-71677-8_26 . ISBN 978-3-540-71677-8 .
^ Перейти обратно: ^а ^б Percy++/PIR на C++ на SourceForge
^ Ди Крещенцо, Джованни; Малкин, Таль; Островский, Рафаил (2000). «Получение частной информации из единой базы данных подразумевает незаметную передачу». Еврокрипт 2000 . ЛНКС. Том. 1807. Спрингер. стр. 122–138. дои : 10.1007/3-540-45539-6_10 .
^ Исайя, Жюваль; Кушилевиц, Эяль; Островский, Рафаэль (2005). «Достаточные условия для устойчивого к коллизиям хеширования». Материалы второй конференции по теории криптографии . Кембридж, Массачусетс, США: Springer-Publishing. стр. 100-1 445–456. дои : 10.1007/978-3-540-30576-7_24 . ISBN 978-3-540-30576-7 .
^ Перейти обратно: ^а ^б Сен-Жан, Фелипе (2005). «Реализация Java вычислительно симметричного протокола поиска частной информации (cSPIR) в одной базе данных» (PDF) . Технический отчет Йельского университета YALEU/DCS/TR-1333 .
^ «Демо-версия MuchPIR» . 14 сентября 2021 г.
^ «СилПИР» . Гитхаб . Проверено 7 июня 2018 г.
^ «Попкорн» (PDF) . Архивировано из оригинала (PDF) 21 августа 2016 г. Проверено 26 мая 2016 г.
^ «шифровальная группа/RAID-PIR» . Гитхаб . Проверено 26 мая 2016 г.
^ «XPIR-команда/XPIR» . Гитхаб . Проверено 26 мая 2016 г.
^ «упПИР» . uppir.poly.edu . Архивировано из оригинала 25 июня 2016 г. Проверено 26 мая 2016 г.

См. также

Ссылки

А. Беймель, Ю. Ишаи, Э. Кушилевиц и Ж.-Ф. Раймонд. нарушение $O(n^{1/(2k-1)})$ барьер для теоретико-информационного поиска частной информации. Материалы 43-го ежегодного симпозиума IEEE по основам компьютерных наук , Ванкувер, Канада, страницы 261–270, 2002 г.
А. Беймель и Ю. Шталь, Надежный поиск частной информации с помощью теории информации , в материалах 3-й Международной конференции по безопасности в сетях связи (SCN'02), стр. 326–341, 2003 г. Цитируется из DGH 2012, op. цит.
[DGH 2012] Кейси Девет, Ян Голдберг и Надя Хенингер , Оптимально надежный поиск частной информации , 21-й симпозиум по безопасности USENIX, август 2012 г.
[AG 2007] К. Агилар-Мельчор и П. Габорит. Эффективный с точки зрения вычислений протокол поиска частной информации на основе решетки , Западноевропейский семинар по исследованиям в области криптологии (WEWoRC), 2007 г.
[CGKS 1998] Б. Чор, О. Голдрейх, Э. Кушилевиц и М. Судан, Поиск частной информации , Журнал ACM, 45(6):965–981, 1998.
[Гольдберг 2007] И. Голдберг, Повышение надежности поиска частной информации , Симпозиум IEEE по безопасности и конфиденциальности (S&P), 2007.
[HOG 2011] Р. Генри, Ф. Олюмофин и И. Голдберг, Практический PIR для электронной коммерции , Конференция ACM по компьютерной и коммуникационной безопасности (CCS), 2011.
[LG 2015] В. Люкс и И. Голдберг, Сублинейное масштабирование для многоклиентского поиска частной информации , Международная конференция по финансовой криптографии и безопасности данных (FC), 2015.
[DHS 2014] Д. Деммлер, А. Герцберг и Т. Шнайдер, RAID-PIR: Практический многосерверный PIR , Семинар по безопасности облачных вычислений (CCSW), 2014.
[ABFK 2014] К. Агилар-Мельчор, Ж. Барьер, Л. Фусс и М.-О. Киллиджиан, «XPIR: поиск частной информации для всех», Архив Cryptology ePrint, отчет 2014/1025, 2014 г.
[GCMSAW 2016] Т. Гупта, Н. Крукс, В. Малхерн, С. Сетти, Л. Алвиси и М. Уолфиш, [1] Масштабируемое и частное потребление медиа с помощью попкорна. USENIX NSDI, март 2016 г.
[Каппос 2013] Дж. Каппос, Как избежать теоретической оптимальности для эффективного и конфиденциального получения обновлений безопасности , Международная конференция по финансовой криптографии и безопасности данных (FC), 2013.
Сергей Еханин. Новые локально декодируемые коды и схемы поиска частной информации, ECCC TR06-127 , 2006 г.
[ACLS 2018] С. Анхель, Х. Чен, К. Лейн, С. Сетти, PIR со сжатыми запросами и амортизированной обработкой запросов , Симпозиум IEEE по безопасности и конфиденциальности (S&P), 2018.

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

[1] Баумелер, Эмин; Бродбент, Энн (17 апреля 2014 г.). «Квантовый поиск частной информации имеет линейную коммуникационную сложность». Журнал криптологии . 28 : 161–175. arXiv : 1304.5490 . дои : 10.1007/s00145-014-9180-2 . S2CID 1450526 .

[ChoKusGolSud98-2] Перейти обратно: ^а ^б Чор, Бенни ; Кушилевиц, Эяль; Гольдрейх, Одед; Судан, Мадху (1 ноября 1998 г.). «Поиск частной информации» (PDF) . Журнал АКМ . 45 (6): 965–981. CiteSeerX 10.1.1.51.3663 . дои : 10.1145/293347.293350 . S2CID 544823 .

[KusOst97-3] Перейти обратно: ^а ^б ^с Кушилевиц, Эяль; Островский, Рафаил (1997). «Репликация не нужна: единая база данных, получение конфиденциальной информации». Материалы 38-го ежегодного симпозиума по основам информатики . Майами-Бич, Флорида, США: Компьютерное общество IEEE. стр. 364–373. CiteSeerX 10.1.1.56.2667 . дои : 10.1109/SFCS.1997.646125 . ISBN 978-0-8186-8197-4 . S2CID 11000506 .

[4] Кашен, Кристиан; Микали, Сильвио; Стадлер, Маркус (1999). «Вычислительный поиск конфиденциальной информации с помощью полилогарифмической связи». Достижения в криптологии – EUROCRYPT '99 . Прага, Чехия: Springer-Verlag. стр. 402–414. дои : 10.1007/3-540-48910-X_28 . ISBN 978-3-540-48910-8 .

[Lip04-5] Перейти обратно: ^а ^б Липмаа, Хельгер (2005). «Забывчивый протокол передачи с логарифмической связью». Материалы 8-й Международной конференции по информационной безопасности (ISC 2005) . Конспекты лекций по информатике. Том. 3650. Сингапур: Springer-Verlag. стр. 314–328. CiteSeerX 10.1.1.73.8768 . дои : 10.1007/11556992_23 . ISBN 978-3-540-31930-6 .

[6] Джентри, Крейг; Рамзан, Зульфикар (2005). «Поиск частной информации из одной базы данных с постоянной скоростью передачи данных». ИКАЛП . ЛНКС. Том. 3580. Спрингер. стр. 803–815. CiteSeerX 10.1.1.113.6572 . дои : 10.1007/11523468_65 .

[7] Киайас, Аггелос; Леонардос, Никос; Липмаа, Хельгер; Павлик, Катерина; Тан, Цян (2015). «Оптимальная скорость получения частной информации с помощью гомоморфного шифрования». Труды по технологиям повышения конфиденциальности 2015 . Том. 2015. ДЕ ГРУЙТЕР. стр. 222–243. дои : 10.1515/popets-2015-0016 . hdl : 20.500.11820/0f84afcb-8ee1-4744-a2ba-4642104c51c5 .

[Lip09-8] Перейти обратно: ^а ^б Липмаа, Хельгер (2010). «Первый протокол CPIR с вычислениями, зависящими от данных». Материалы 12-й Международной конференции по информационной безопасности и криптологии . Конспекты лекций по информатике. Том. 5984. Сеул, Корея: Springer-Verlag. стр. 193–210. CiteSeerX 10.1.1.215.7768 . дои : 10.1007/978-3-642-14423-3_14 . ISBN 978-3-642-14423-3 .

[9] Ишаи, Юваль; Кушилевиц, Эяль; Островский, Рафаил; Сахай, Амит (2004). «Батч-коды и их применение» (PDF) . СТОК'04 . АКМ. стр. 262–271. дои : 10.1145/1007352.1007396 . Проверено 23 октября 2015 г.

[10] Островский, Рафаил; Скейт III; Уильям Э. (2007). «Обзор поиска частной информации из одной базы данных: методы и приложения». Материалы 10-й Международной конференции по практике и теории криптографии с открытым ключом . Спрингер-Верлаг. стр. 393–411. дои : 10.1007/978-3-540-71677-8_26 . ISBN 978-3-540-71677-8 .

[:0-11] Перейти обратно: ^а ^б Percy++/PIR на C++ на SourceForge

[12] Ди Крещенцо, Джованни; Малкин, Таль; Островский, Рафаил (2000). «Получение частной информации из единой базы данных подразумевает незаметную передачу». Еврокрипт 2000 . ЛНКС. Том. 1807. Спрингер. стр. 122–138. дои : 10.1007/3-540-45539-6_10 .

[13] Исайя, Жюваль; Кушилевиц, Эяль; Островский, Рафаэль (2005). «Достаточные условия для устойчивого к коллизиям хеширования». Материалы второй конференции по теории криптографии . Кембридж, Массачусетс, США: Springer-Publishing. стр. 100-1 445–456. дои : 10.1007/978-3-540-30576-7_24 . ISBN 978-3-540-30576-7 .

[TR1-14] Перейти обратно: ^а ^б Сен-Жан, Фелипе (2005). «Реализация Java вычислительно симметричного протокола поиска частной информации (cSPIR) в одной базе данных» (PDF) . Технический отчет Йельского университета YALEU/DCS/TR-1333 .

[15] «Демо-версия MuchPIR» . 14 сентября 2021 г.

[16] «СилПИР» . Гитхаб . Проверено 7 июня 2018 г.

[17] «Попкорн» (PDF) . Архивировано из оригинала (PDF) 21 августа 2016 г. Проверено 26 мая 2016 г.

[18] «шифровальная группа/RAID-PIR» . Гитхаб . Проверено 26 мая 2016 г.

[19] «XPIR-команда/XPIR» . Гитхаб . Проверено 26 мая 2016 г.

[20] «упПИР» . uppir.poly.edu . Архивировано из оригинала 25 июня 2016 г. Проверено 26 мая 2016 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]