Интернет магазин китайских планшетных компьютеров

Компьютеры - Получение скрытой информации

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

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

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

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