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

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

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

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


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

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

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