Получение скрытой информации
Получение скрытой информации (англ. Private information retrieval (PIR))
В криптографии, протокол поиска информации (PIR) позволяет потребителю (или игроку) получить интересующую его частную информацию с сервера. Причём сервер не сможет распознать какая именно часть его информации стала известна игроку. Задача : Есть база данных состоящая из <math>n</math> битов. Есть игрок, который хочет достать бит номер <math>i</math> так чтобы база данных содержащая все <math>n</math> битов не смогла узнать никакой информации какой именно бит достал игрок.
Тривиальное (но не эффективное) решение состоит в посылке всех <math>n</math> битов игроку, включая искомый им <math>i</math>-бит. Другой путь — использование PIR-протокола где игрок задаёт вопрос (функцию) базе данных. Последняя берёт эту функцию, прилагает её ко всей совокупности базы данных и получает ответ, который высылается обратно игроку. Условия этой игры следующие:
1) Длина суммы вопроса (функции) и ответа должна быть много меньше чем n.
2) игрок должен для любого <math>i</math> послать такой вопрос, чтобы ответ был правильный, то есть <math>i</math>-бит был верно получен.
3) База данных не может ничего узнать по поводу <math>i</math>.
Постановка задачи для нескольких копий базы данных была впервые сформулирована Шором, Голдрайхом, Кушелевицем и Суданом в 1996 г. Авторы предложили решение [web.archive.org/web/20040327173643/www.cs.technion.ac.il/~benny/PIR.pdf] которое требовало нескольких копий базы данных -- и чтобы серверы, держащие эти копии, не имели права друг с другом общаться.
Впервые решение той же задачи для одного сервера и одного игрока дали Эйал Кушелевиц и Рафаил Островский в 1997 г. Они показали [www.cs.ucla.edu/~rafail/PUBLIC/34.pdf] что длина суммы вопроса и ответа равна <math>O(n^\epsilon)</math> для любого <math>\epsilon > 0</math>. Указанные работы дали толчок интенсивному развитию данного раздела [en.wikipedia.org/wiki/Private_information_retrieval Private Information Retrieval].
См. также
Напишите отзыв о статье "Получение скрытой информации"
Отрывок, характеризующий Получение скрытой информации
Каратаев, по случаю тепла и для удобства работы, был в одних портках и в черной, как земля, продранной рубашке. Волоса его, как это делают мастеровые, были обвязаны мочалочкой, и круглое лицо его казалось еще круглее и миловиднее.– Уговорец – делу родной братец. Как сказал к пятнице, так и сделал, – говорил Платон, улыбаясь и развертывая сшитую им рубашку.
Француз беспокойно оглянулся и, как будто преодолев сомнение, быстро скинул мундир и надел рубаху. Под мундиром на французе не было рубахи, а на голое, желтое, худое тело был надет длинный, засаленный, шелковый с цветочками жилет. Француз, видимо, боялся, чтобы пленные, смотревшие на него, не засмеялись, и поспешно сунул голову в рубашку. Никто из пленных не сказал ни слова.
– Вишь, в самый раз, – приговаривал Платон, обдергивая рубаху. Француз, просунув голову и руки, не поднимая глаз, оглядывал на себе рубашку и рассматривал шов.
– Что ж, соколик, ведь это не швальня, и струмента настоящего нет; а сказано: без снасти и вша не убьешь, – говорил Платон, кругло улыбаясь и, видимо, сам радуясь на свою работу.
– C'est bien, c'est bien, merci, mais vous devez avoir de la toile de reste? [Хорошо, хорошо, спасибо, а полотно где, что осталось?] – сказал француз.
– Она еще ладнее будет, как ты на тело то наденешь, – говорил Каратаев, продолжая радоваться на свое произведение. – Вот и хорошо и приятно будет.
– Merci, merci, mon vieux, le reste?.. – повторил француз, улыбаясь, и, достав ассигнацию, дал Каратаеву, – mais le reste… [Спасибо, спасибо, любезный, а остаток то где?.. Остаток то давай.]
Пьер видел, что Платон не хотел понимать того, что говорил француз, и, не вмешиваясь, смотрел на них. Каратаев поблагодарил за деньги и продолжал любоваться своею работой. Француз настаивал на остатках и попросил Пьера перевести то, что он говорил.
