Введение
В криптографии, протокол частного извлечения информации (PIR) — это протокол, позволяющий пользователю получить элемент из базы данных, хранящейся на сервере, не раскрывая, какой именно элемент был запрошен. PIR является ослабленной версией протокола "один из n" с неотслеживаемой передачей, где также требуется, чтобы пользователь не получал никакой информации о других элементах базы данных. Тривиальный, но крайне неэффективный способ реализации PIR — это отправка сервером пользователю полной копии базы данных. Фактически, это единственный возможный протокол (в классической или квантовой модели) обеспечивающий пользователю теоретически полную конфиденциальность запроса при использовании одного сервера. Существует два подхода к решению этой проблемы: ограничить вычислительные возможности сервера или предположить наличие нескольких некоординированных серверов, каждый из которых хранит копию базы данных. Проблема была впервые сформулирована в 1995 году Чором, Голдрейхом, Кушилевицем и Суданом. С тех пор были разработаны высокоэффективные решения. Реализация PIR для одной базы данных (с вычислительной конфиденциальностью) может быть достигнута с постоянным (амортизированным) объемом обмена данными, а для k баз данных (с информационно-теоретической конфиденциальностью) — с объемом обмена данными .
In cryptography, a private information retrieval (PIR) protocol is a protocol that allows a user to retrieve an item from a server in possession of a database without revealing which item is retrieved. PIR is a weaker version of 1 out of n oblivious transfer, where it is also required that the user should not get information about other database items. One trivial, but very inefficient way to achieve PIR is for the server to send an entire copy of the database to the user. In fact, this is the only possible protocol (in the classical or the quantum setting) that gives the user information theoretic privacy for their query in a single server setting. There are two ways to address this problem: make the server computationally bounded or assume that there are multiple non cooperating servers, each having a copy of the database. The problem was introduced in 1995 by Chor, Goldreich, Kushilevitz and Sudan Since then, very efficient solutions have been discovered. Single database (computationally private) PIR can be achieved with constant (amortized) communication and k database (information theoretic) PIR can be done with communication.
Связь с другими криптографическими примитивами
Односторонние функции необходимы, но не доказано, что они достаточны для вычислительного извлечения частной информации из единой базы данных, при условии, что коммуникация сублинейна. Фактически, Джованни Ди Кресценцо, Тал Малкин и Рафаил Островский доказали, что такой протокол влечет за собой протокол слепой передачи (см. ниже). Слепая передача, также называемая симметричной PIR, представляет собой PIR с дополнительным ограничением, что пользователь не должен получать никакой информации, кроме запрошенного элемента. Она называется симметричной, поскольку требования к конфиденциальности предъявляются как к пользователю, так и к базе данных. Как показали Ишай, Кушилевиц и Островский, любая схема вычислительного PIR, реализуемая за один раунд, влечет за собой существование криптографических хеш-функций, устойчивых к коллизиям.
Изменения PIR
Основная мотивация для Private Information Retrieval – это семейство двухсторонних протоколов, в которых одна из сторон (отправитель) владеет базой данных, а другая сторона (получатель) хочет запросить её с определенными ограничениями и гарантиями конфиденциальности. Таким образом, в результате протокола, если получатель хочет получить i-е значение в базе данных, он должен узнать i-ую запись, но отправитель не должен узнать ничего о значении i. В общем протоколе PIR вычислительно неограниченный отправитель не должен узнать ничего о i, поэтому конфиденциальность теоретически сохраняется. С момента постановки задачи PIR было предпринято несколько подходов к её решению и предложено ряд вариаций. Протокол CPIR (Computationally Private Information Retrieval) аналогичен протоколу PIR: получатель извлекает из базы данных отправителя элемент, выбранный им, таким образом, чтобы отправитель не получил никаких сведений о том, какой элемент был передан. Протокол CSPIR (Computationally Symmetric Private Information Retrieval) используется в аналогичном сценарии, в котором используется протокол CPIR. Если отправитель владеет базой данных, а получатель хочет получить i-е значение в этой базе данных, то по окончании выполнения протокола SPIR получатель не должен узнать ничего о значениях в базе данных, кроме i-го. Является реализацией CPIR в виде расширения Postgres C/C++ [GitHub, 2021]. SealPIR – это быстрая реализация CPIR [ACLS 2018]. Popcorn – это реализация PIR, адаптированная для медиа [GCMSAW 2016]. Percy++ является реализацией схемы ITPIR [DHS 2014]. XPIR – это быстрая реализация CPIR [ABFK 2014]. upPIR – это реализация ITPIR [Cappos 2013].