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

Получение скрытой информации (англ. Private information retrieval (PIR))

В криптографии, протокол поиска информации (PIR) позволяет потребителю (или игроку) получить интересующую его частную информацию с сервера. Причём сервер не сможет распознать какая именно часть его информации стала известна игроку. Задача : Есть база данных состоящая из ${\displaystyle n}$ битов. Есть игрок, который хочет достать бит номер ${\displaystyle i}$ так чтобы база данных содержащая все ${\displaystyle n}$ битов не смогла узнать никакой информации какой именно бит достал игрок. Тривиальное (но не эффективное) решение состоит в посылке всех ${\displaystyle n}$ битов игроку, включая искомый им ${\displaystyle i}$-бит. Другой путь — использование PIR-протокола где игрок задаёт вопрос (функцию) базе данных. Последняя берёт эту функцию, прилагает её ко всей совокупности базы данных и получает ответ, который высылается обратно игроку. Условия этой игры следующие:
1) Длина суммы вопроса (функции) и ответа должна быть много меньше чем n.
2) игрок должен для любого ${\displaystyle i}$ послать такой вопрос, чтобы ответ был правильный, то есть ${\displaystyle i}$-бит был верно получен.
3) База данных не может ничего узнать по поводу ${\displaystyle i}$.

Постановка задачи для нескольких копий базы данных была впервые сформулирована Шором, Голдрайхом, Кушелевицем и Суданом в 1996 г. Авторы предложили решение которое требовало нескольких копий базы данных -- и чтобы серверы, держащие эти копии, не имели права друг с другом общаться.

Впервые решение той же задачи для одного сервера и одного игрока дали Эйал Кушелевиц и Рафаил Островский в 1997 г. Они показали что длина суммы вопроса и ответа равна ${\displaystyle O(n^{\epsilon })}$ для любого ${\displaystyle \epsilon >0}$. Указанные работы дали толчок интенсивному развитию данного раздела Private Information Retrieval.