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

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

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

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

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

См. также

• Защита персональных данных
• Информационная безопасность
• Тайна связи