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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Получение скрытой информации (англ. 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.

См. также[править | править вики-текст]