В криптографии , частная информация поиск (PIR) это протокол , который позволяет пользователю получить элемент из сервера владения базы данных , не раскрывая , какой элемент извлекаются. PIR более слабая версия 1-внеконкурсных п рассеянной передачи , где также требуется , чтобы пользователь не должен получать информацию о других элементов базы данных.
Один тривиальный, но очень неэффективный способ достижения PIR - это отправка сервером полной копии базы данных пользователю. Фактически, это единственный возможный протокол (в классической или квантовой среде [1] ), который дает пользователю теоретическую конфиденциальность информации для его запроса в условиях одного сервера. [2] Есть два способа решить эту проблему: сделать сервер вычислительно ограниченным или предположить, что существует несколько не взаимодействующих серверов, каждый из которых имеет копию базы данных.
Проблема была представлена в 1995 г. Чором, Гольдрайхом, Кушилевицем и Суданом [2] в теоретико-информационной постановке и в 1997 г. Кушилевицем и Островским в вычислительной постановке. [3] С тех пор были обнаружены очень эффективные решения. Единая база данных (вычислительно частная) PIR может быть достигнута с помощью постоянной (амортизированной) связи, а k-база данных (теоретическая информация) PIR может быть выполнена с коммуникация.
Достижения в вычислительной PIR
Первая вычислительная схема PIR с единой базой данных для достижения сложности связи менее был создан в 1997 году Кушилевицем и Островским [3] и достиг коммуникативной сложности для любой , где - количество бит в базе данных. Безопасность их схемы была основана на хорошо изученной проблеме квадратичной остаточности . В 1999 году Кристиан Качин, Сильвио Микали и Маркус Стадлер [4] достигли полилогарифмической сложности коммуникации. Безопасность их системы основана на предположении о сокрытии фи . В 2004 году Хельгер Липмаа [5] достиг логарифмической сложности коммуникации., где это длина струн и - параметр безопасности. Безопасность его системы сводится к семантической безопасности гибкой по длине аддитивно гомоморфной криптосистемы, такой как криптосистема Дамгарда-Юрика . В 2005 году Крейг Джентри и Зульфикар Рамзан [6] достигли логарифмической сложности связи, которая извлекает логарифмические (последовательные) биты базы данных. Безопасность их схемы также основана на предположении о сокрытии Phi. Скорость связи наконец снизилась доот Aggelos Kiayias , Nikos Leonardos , Helger Lipmaa , Екатерина Павликом , Цян Тан , в 2015 году [7]
Все предыдущие вычислительные протоколы PIR с сублинейной связью требовали линейной вычислительной сложности операции с открытым ключом. В 2009 году Хельгер Липмаа [8] разработал вычислительный протокол PIR со сложностью связи. и вычисление наихудшего случая операции с открытым ключом. Методы амортизации, извлекающие непоследовательных биты были рассмотрены Юваль Ишай , Эяль Kushilevitz , Рафаил Островский и Amit Сахай . [9]
Как показали Островский и Скейт [10], схемы Кушилевица и Островского [3] и Липмаа [5] используют аналогичные идеи, основанные на гомоморфном шифровании . Протокол Кушилевица и Островского основан на криптосистеме Голдвассера-Микали, а протокол Липмаа основан на криптосистеме Дамгарда-Юрика .
Достижения в области теории информации PIR
Достижение теоретической информационной безопасности требует предположения, что существует несколько не взаимодействующих серверов, каждый из которых имеет копию базы данных. Без этого предположения любой теоретически безопасный протокол PIR требует объема обмена данными, который по крайней мере равен размеру базы данных n . Многосерверные протоколы PIR, устойчивые к неотвечающим или злонамеренным / вступающим в сговор серверам, называются надежными или византийскими надежными соответственно. Эти вопросы впервые были рассмотрены Беймелем и Шталом (2002). -Серверная система, которая может работать там, где отвечают только k серверов, ν серверов отвечают неправильно, и которая может противостоять до t серверов в сговоре без раскрытия запроса клиента, называется " t -private ν-Byzantine robust k -out". -оф-ℓ ПИР »[DGH 2012]. В 2012 году К. Девет, И. Голдберг и Н. Хенингер (DGH 2012) предложили оптимально надежную схему, которая является византийско-устойчивой длячто является теоретическим максимальным значением. Он основан на более раннем протоколе Голдберга, который использует секретное совместное использование Шамира, чтобы скрыть запрос. Голдберг выпустил реализацию C ++ на Sourceforge . [11]
Отношение к другим криптографическим примитивам
Односторонние функции необходимы, но недостаточно известны для нетривиального (например, с сублинейной связью) поиска конфиденциальной в вычислительном отношении информации из одной базы данных. Фактически, такой протокол, как доказали Джованни Ди Крещенцо , Тал Малкин и Рафаил Островский, подразумевает незаметную передачу (см. Ниже). [12]
Невидимая передача , также называемая симметричной PIR, - это PIR с дополнительным ограничением, заключающимся в том, что пользователь не может изучать какой-либо элемент, кроме того, который он запросил. Это называется симметричным, потому что и у пользователя, и у базы данных есть требования к конфиденциальности.
Устойчивые к коллизиям криптографические хеш-функции подразумеваются любой одноэтапной вычислительной схемой PIR, как показано Ишаем, Кушилевицем и Островским. [13]
Варианты PIR
Основная мотивация для поиска частной информации - это семейство двусторонних протоколов, в которых одна из сторон ( отправитель ) владеет базой данных, а другая часть ( получатель ) хочет запросить ее с определенными ограничениями и гарантиями конфиденциальности. Итак, в результате протокола, если получатель хочет получить i-е значение в базе данных, он должен узнать i-ю запись, но отправитель не должен ничего узнавать о i . В общем протоколе PIR вычислительно неограниченный отправитель ничего не может узнать о i, поэтому конфиденциальность теоретически сохраняется. С тех пор, как была поставлена проблема PIR, были предложены разные подходы к ее решению и были предложены некоторые варианты.
Протокол CPIR (Computationally Private Information Retrieval) аналогичен протоколу PIR: получатель извлекает выбранный им элемент из базы данных отправителя, так что отправитель не получает информации о том, какой элемент был передан. [8] Единственное отличие состоит в том, что конфиденциальность защищена от полиномиально ограниченного отправителя. [14]
Протокол CSPIR (вычислительно симметричное извлечение частной информации) используется в аналогичном сценарии, в котором используется протокол CPIR. Если отправитель владеет базой данных, а получатель хочет получить i-е значение в этой базе данных, в конце выполнения протокола SPIR получатель не должен был ничего узнавать о значениях в базе данных, кроме i-го. один. [14]
Реализации PIR
В литературе были реализованы многочисленные вычислительные схемы PIR и теоретико-информационные PIR. Вот неполный список:
- Percy ++ [11] включает реализации [AG 2007, DGH 2012, CGKS 1998, Goldberg 2007, HOG 2011, LG 2015].
- Popcorn [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].
Заметки
- ^ Баумелер, Эмин; Бродбент, Энн (17 апреля 2014 г.). «Квантовый поиск частной информации имеет линейную коммуникационную сложность». Журнал криптологии . 28 : 161–175. arXiv : 1304,5490 . DOI : 10.1007 / s00145-014-9180-2 .
- ^ а б Чор, Бенни; Кушилевиц, Эяль; Гольдрайх, Одед; Судан, Мадху (1 ноября 1998 г.). «Поиск частной информации» (PDF) . Журнал ACM . 45 (6): 965–981. CiteSeerX 10.1.1.51.3663 . DOI : 10.1145 / 293347.293350 .
- ^ а б в Кушилевиц, Эяль; Островский, Рафаил (1997). «Репликация не требуется: единая база данных, поиск приватно-вычислительной информации». Материалы 38-го ежегодного симпозиума по основам информатики . Майами-Бич, Флорида, США: Компьютерное общество IEEE. С. 364–373. CiteSeerX 10.1.1.56.2667 . DOI : 10.1109 / SFCS.1997.646125 . ISBN 978-0-8186-8197-4.
- ^ Качин, Кристиан; Микали, Сильвио; Стадлер, Маркус (1999). «Вычислительный поиск частной информации с полилогарифмической связью». Достижения в криптологии - EUROCRYPT '99 . Прага, Чехия: Springer-Verlag. С. 402–414. DOI : 10.1007 / 3-540-48910-X_28 . ISBN 978-3-540-48910-8.
- ^ а б Липмаа, Хельгер (2005). «Незаметный протокол передачи с лог-квадратом связи». Материалы 8-й Международной конференции по информационной безопасности (ISC 2005) . Конспект лекций по информатике. 3650 . Сингапур: Спрингер-Верлаг. С. 314–328. CiteSeerX 10.1.1.73.8768 . DOI : 10.1007 / 11556992_23 . ISBN 978-3-540-31930-6.
- ^ Джентри, Крейг; Рамзан, Зульфикар (2005). «Поиск частной информации из одной базы данных с постоянной скоростью передачи данных». ИКАЛП . LNCS. 3580 . Springer. С. 803–815. CiteSeerX 10.1.1.113.6572 . DOI : 10.1007 / 11523468_65 .
- ^ Киаиас, Аггелос; Леонардос, Никос; Липмаа, Хельгер; Павлик, Екатерина; Тан, Цян (2015). «Оптимальная скорость извлечения частной информации из гомоморфного шифрования». Труды по технологиям повышения конфиденциальности 2015 . 2015 . ДЕ ГРЮЙТЕР. С. 222–243. DOI : 10.1515 / попец-2015-0016 .
- ^ а б Липмаа, Хельгер (2010). «Первый протокол CPIR с вычислением, зависящим от данных». Материалы 12-й Международной конференции по информационной безопасности и криптологии . Конспект лекций по информатике. 5984 . Сеул, Корея: Springer-Verlag. С. 193–210. CiteSeerX 10.1.1.215.7768 . DOI : 10.1007 / 978-3-642-14423-3_14 . ISBN 978-3-642-14423-3.
- ^ Ишай, Юваль; Кушилевиц, Эяль; Островский, Рафаил; Сахай, Амит (2004). «Пакетные коды и их приложения» (PDF) . STOC'04 . ACM. С. 262–271. DOI : 10.1145 / 1007352.1007396 . Проверено 23 октября 2015 .
- ^ Островский, Рафаил; Скейт III; Уильям Э. (2007). «Обзор поиска частной информации с единой базой данных: методы и приложения». Материалы 10-й Международной конференции по практике и теории криптографии с открытым ключом . Springer-Verlag. С. 393–411. DOI : 10.1007 / 978-3-540-71677-8_26 . ISBN 978-3-540-71677-8.
- ^ a b Percy ++ / PIR на C ++ в SourceForge
- ^ Ди Крещенцо, Джованни; Малкин, Таль; Островский, Рафаил (2000). «Поиск частной информации из единой базы данных подразумевает передачу без внимания». Еврокрипт 2000 . LNCS. 1807 . Springer. С. 122–138. DOI : 10.1007 / 3-540-45539-6_10 .
- ^ Ишай, Юваль; Кушилевиц, Эяль; Островский, Рафаил (2005). «Достаточные условия для стойкого к коллизиям хеширования». Труды Второй конференции по теории криптографии . Кембридж, Массачусетс, США: Springer-Verlag. С. 445–456. DOI : 10.1007 / 978-3-540-30576-7_24 . ISBN 978-3-540-30576-7.
- ^ а б Сен-Жан, Фелипе (2005). «Реализация Java протокола вычислительно симметричного поиска частной информации для одной базы данных (cSPIR)» (PDF) . Технический отчет Йельского университета YALEU / DCS / TR-1333 .
- ^ «Попкорн» (PDF) . Архивировано из оригинального (PDF) 21 августа 2016 года . Проверено 26 мая 2016 .
- ^ «Шифровальная группа / RAID-ПИР» . GitHub . Проверено 26 мая 2016 .
- ^ «СилПИР» . Github . Проверено 7 июня 2018 .
- ^ «УпПИР» . uppir.poly.edu . Архивировано из оригинала на 2016-06-25 . Проверено 26 мая 2016 .
- ^ «XPIR-team / XPIR» . GitHub . Проверено 26 мая 2016 .
Смотрите также
- k-анонимность
- Локально декодируемый код
Рекомендации
- А. Беймель, Ю. Ишай, Э. Кушилевиц, Ж.-Ф. Раймонд. Нарушениебарьер для поиска частной информации теоретико-информационного характера. Материалы 43-го ежегодного симпозиума IEEE по основам компьютерных наук , Ванкувер, Канада, страницы 261-270, 2002.
- A. Beimel и Y. Stahl, Надежный теоретико-информационный поиск частной информации , в 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] К. Агилар-Мельчор и П. Габорит. Основанный на решетке эффективный с вычислительной точки зрения протокол поиска частной информации , Western European Workshop on Research in Cryptology (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] Масштабируемое и частное потребление медиа с помощью Popcorn. USENIX NSDI, март 2016 г.
- [Cappos 2013] Дж. Каппос, Как избежать теоретической оптимальности для эффективного и конфиденциального получения обновлений безопасности , Международная конференция по финансовой криптографии и безопасности данных (FC), 2013.
- Сергей Еханин. Новый локально декодируемые коды и приватной информации поисковые схемы, ECCC TR06-127 , 2006.
- [ACLS 2018] С. Ангел, Х. Чен, К. Лайне, С. Сетти, PIR со сжатыми запросами и амортизированной обработкой запросов , Симпозиум IEEE по безопасности и конфиденциальности (S&P), 2018.
Внешние ссылки
- Ссылки на веб-сайты Хельгера Липмаа о передаче без внимания и PIR
- Веб-сайт Уильяма Гасарха на PIR, включая обзорные статьи
- Сайт Рафаила Островского, на котором размещены статьи и обзоры ПИРа.