Получение скрытой информации
Материал из Википедии — свободной энциклопедии
Получение скрытой информации (англ. Private information retrieval (PIR))
В криптографии, протокол поиска информации (PIR) позволяет потребителю (или игроку) получить интересующую его частную информацию с сервера. Причём сервер не сможет распознать какая именно часть его информации стала известна игроку. Задача : Есть база данных состоящая из n битов. Есть игрок, который хочет достать бит номер i так чтобы база данных содержащая все n битов не смогла узнать никакой информации какой именно бит достал игрок. Тривиальное (но не эффективное) решение состоит в посылке всех n битов игроку, включая искомый им i-бит. Другой путь — использование PIR-протокола где игрок задаёт вопрос (функцию) базе данных. Последняя берёт эту функцию, прилагает её ко всей совокупности базы данных и получает ответ, который высылается обратно игроку. Условия этой игры следующие:
1) Длина суммы вопроса (функции) и ответа должна быть много меньше чем n.
2) игрок должен для любого i послать такой вопрос, чтобы ответ был правильный, то есть i-бит был верно получен.
3) База данных не может ничего узнать по поводу i.
Постановка задачи была впервые сформулирована Шором, Голдрайхом, Кушелевицем и Суданом в 1996 г. Авторы предложили решение [1] которое требовало нескольких копий базы данных -- и чтобы серверы, держащие эти копии, не имели права друг с другом общаться.
Впервые решение той же задачи для одного сервера и одного игрока дали Эйал Кушелевиц и Рафаил Островский в 1997 г. Они показали [2], что длина суммы вопроса и ответа равна O(nε) для любого ε > 0. Указанные работы дали толчок интенсивному развитию данного раздела Private Information Retrieval.