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

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

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

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

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

Первая вычислительная схема PIR с одной базой данных для достижения сложности связи менее был создан в 1997 году Кушилевицем и Островским [3] и достигла коммуникационной сложности для любого , куда - количество бит в базе данных. Безопасность их схемы была основана на хорошо изученных Проблема квадратичной остаточности. В 1999 году Кристиан Качин, Сильвио Микали и Маркус Стадлер[4] достигнута полилогарифмическая коммуникационная сложность. Безопасность их системы основана на Предположение о сокрытии фи. В 2004 г. Хельгер Липмаа [5] достигнутая логарифмическая сложность связи , куда длина струн и - параметр безопасности. Безопасность его системы сводится к семантическая безопасность гибкой по длине аддитивно гомоморфной криптосистемы, такой как Криптосистема Дамгарда – Юрика. В 2005 году Крейг Джентри и Зульфикар Рамзан [6] достигнута сложность связи с лог-квадратом, которая извлекает лог-квадрат (последовательные) биты базы данных. Безопасность их схемы также основана на варианте предположения о сокрытии Phi. Скорость связи наконец снизилась до к Аггелос Киаиас, Никос Леонардос, Хельгер Липмаа, Екатерина Павлик, Цян Тан, в 2015 г. [7].

Все предыдущие вычислительные протоколы PIR с сублинейной связью требовали линейной вычислительной сложности операции с открытым ключом. В 2009, Хельгер Липмаа [8] разработал вычислительный протокол PIR со сложностью связи и вычисление наихудшего случая операции с открытым ключом. Методы амортизации, которые извлекают непоследовательные биты, были рассмотрены Юваль Ишай, Эял Кушилевиц, Рафаил Островский и Амит Сахаи.[9]

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

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

Достижение теоретической информационной безопасности требует предположения, что существует несколько не взаимодействующих серверов, каждый из которых имеет копию базы данных. Без этого предположения любой теоретически безопасный протокол PIR требует объема обмена данными, который не меньше размера базы данных. п. Многосерверные протоколы PIR, устойчивые к неотвечающим или злонамеренным / вступающим в сговор серверам, называются крепкий или же Византийский крепкий соответственно. Эти вопросы впервые были рассмотрены Беймелем и Шталом (2002). ℓ-серверная система, которая может работать только там, где k серверов отвечают, ν серверов отвечают некорректно, и которые могут выдержать до т сговор серверов без раскрытия запроса клиента называется "т-частный ν-византийский робастный k-out-of-PIR »[DGH 2012]. В 2012 г. К. Девет, И. Голдберг и Н. Хенингер (DGH 2012) предложили оптимально устойчивую схему, которая является византийской устойчивой к что является теоретическим максимальным значением. Он основан на более раннем протоколе Голдберга, который использует Обмен секретами Шамира чтобы скрыть запрос. Голдберг выпустил C ++ реализация на Sourceforge.[11]

Отношение к другим криптографическим примитивам

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

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

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

Варианты PIR

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

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

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

Реализации PIR

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

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

Примечания

  1. ^ Баумелер, Эмин; Бродбент, Энн (17 апреля 2014 г.). «Квантовый поиск частной информации имеет линейную коммуникационную сложность». Журнал криптологии. 28: 161–175. arXiv:1304.5490. Дои:10.1007 / s00145-014-9180-2.
  2. ^ а б Чор, Бенни; Кушилевиц, Эял; Гольдрайх, Одед; Судан, Мадху (1 ноября 1998 г.). «Поиск частной информации» (PDF). Журнал ACM. 45 (6): 965–981. CiteSeerX  10.1.1.51.3663. Дои:10.1145/293347.293350.
  3. ^ а б c Кушилевиц, Эял; Островский, Рафаил (1997). «Репликация не требуется: единая база данных, поиск конфиденциальной вычислительной информации». Материалы 38-го ежегодного симпозиума по основам информатики. Майами-Бич, Флорида, США: Компьютерное общество IEEE. С. 364–373. CiteSeerX  10.1.1.56.2667. Дои:10.1109 / SFCS.1997.646125. ISBN  978-0-8186-8197-4.
  4. ^ Качин, Кристиан; Микали, Сильвио; Стадлер, Маркус (1999). «Вычислительный поиск частной информации с полилогарифмической связью». Достижения в криптологии - EUROCRYPT '99. Прага, Чехия: Springer-Verlag. С. 402–414. Дои:10.1007 / 3-540-48910-X_28. ISBN  978-3-540-48910-8.
  5. ^ а б Липмаа, Хельгер (2005). «Незаметный протокол передачи с лог-квадрат коммуникации». Материалы 8-й Международной конференции по информационной безопасности (ISC 2005). Конспект лекций по информатике. 3650. Сингапур: Спрингер-Верлаг. С. 314–328. CiteSeerX  10.1.1.73.8768. Дои:10.1007/11556992_23. ISBN  978-3-540-31930-6.
  6. ^ Джентри, Крейг; Рамзан, Зульфикар (2005). «Поиск частной информации из одной базы данных с постоянной скоростью передачи данных». ИКАЛП. LNCS. 3580. Springer. С. 803–815. CiteSeerX  10.1.1.113.6572. Дои:10.1007/11523468_65.
  7. ^ Киаиас, Аггелос; Леонардос, Никос; Липмаа, Хельгер; Павлик, Екатерина; Тан, Цян (2015). «Оптимальная скорость извлечения частной информации из гомоморфного шифрования». Труды по технологиям повышения конфиденциальности 2015 г.. 2015. ДЕ ГРЮЙТЕР. С. 222–243. Дои:10.1515 / попец-2015-0016.
  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). STOC'04. ACM. С. 262–271. Дои:10.1145/1007352.1007396. Получено 2015-10-23.
  10. ^ Островский, Рафаил; Скейт III; Уильям Э. (2007). «Обзор поиска частной информации с единой базой данных: методы и приложения». Материалы 10-й Международной конференции по практике и теории криптографии с открытым ключом. Springer-Verlag. С. 393–411. Дои:10.1007/978-3-540-71677-8_26. ISBN  978-3-540-71677-8.
  11. ^ а б Percy ++ / PIR в C ++ в SourceForge
  12. ^ Ди Крещенцо, Джованни; Малкин, Таль; Островский, Рафаил (2000). «Извлечение частной информации из единой базы данных подразумевает передачу без внимания». Еврокрипт 2000. LNCS. 1807. Springer. С. 122–138. Дои:10.1007/3-540-45539-6_10.
  13. ^ Ишай, Юваль; Кушилевиц, Эял; Островский, Рафаил (2005). «Достаточные условия для устойчивого к коллизиям хеширования». Труды Второй конференции по теории криптографии. Кембридж, Массачусетс, США: Springer-Verlag. С. 445–456. Дои:10.1007/978-3-540-30576-7_24. ISBN  978-3-540-30576-7.
  14. ^ а б Сен-Жан, Фелипе (2005). "Реализация Java протокола вычислительно-симметричного поиска частной информации для одной базы данных (cSPIR)" (PDF). Технический отчет Йельского университета YALEU / DCS / TR-1333.
  15. ^ "Попкорн" (PDF). Архивировано из оригинал (PDF) на 21.08.2016. Получено 2016-05-26.
  16. ^ "encryptogroup / RAID-PIR". GitHub. Получено 2016-05-26.
  17. ^ «СилПИР». Github. Получено 2018-06-07.
  18. ^ "upPIR". uppir.poly.edu. Архивировано из оригинал на 2016-06-25. Получено 2016-05-26.
  19. ^ "XPIR-team / XPIR". GitHub. Получено 2016-05-26.

Смотрите также

Рекомендации

  • А. Беймель, Ю. Ишай, Э. Кушилевиц, Ж.-Ф. Раймонд. Нарушение барьер для поиска частной информации теоретико-информационного характера. Материалы 43-го ежегодного симпозиума IEEE по основам компьютерных наук, Ванкувер, Канада, страницы 261-270, 2002.
  • А. Беймель, Ю. Шталь, Надежный поиск частной информации в теории информации, in Proceedings of the 3rd International Conference on Security in Communication Networks (SCN'02), pp. 326–341, 2003. Цитата из DGH 2012, op. соч.
  • [DGH 2012] Кейси Девет, Ян Голдберг, и Надя Хенингер, Оптимально надежный поиск частной информации, 21-й симпозиум по безопасности USENIX, август 2012 г.
  • [AG 2007] К. Агилар-Мельчор и П. Габорит. Эффективный с вычислительной точки зрения протокол поиска частной информации на основе решетки, Западноевропейский семинар по исследованиям в области криптологии (WEWoRC), 2007 г.
  • [CGKS 1998] Б. Чор, О. Гольдрейх, Э. Кушилевиц и М. Судан, Получение частной информации, Журнал ACM, 45 (6): 965–981, 1998.
  • [Goldberg 2007] I. Goldberg, Повышение надежности поиска частной информации, Симпозиум 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 Archive, отчет 2014/1025, 2014.
  • [GCMSAW, 2016] Т. Гупта, Н. Крукс, В. Малхерн, С. Сетти, Л. Алвиси и М. Уолфиш, [1] Масштабируемость и конфиденциальность медиа потребление с попкорном. USENIX NSDI, март 2016 г.
  • [Cappos 2013] Дж. Каппос, Избежание теоретической оптимальности для эффективного и конфиденциального получения обновлений безопасности, Международная конференция по финансовой криптографии и безопасности данных (FC), 2013.
  • Сергей Еханин. Новые локально декодируемые коды и схемы поиска частной информации, ECCC  TR06-127, 2006.
  • [ACLS 2018] С. Ангел, Х. Чен, К. Лайне, С. Сетти, PIR со сжатыми запросами и амортизированной обработкой запросов, Симпозиум IEEE по безопасности и конфиденциальности (S&P), 2018 г.

внешняя ссылка