Интернет магазин китайских планшетных компьютеров |
|
Компьютеры - Доказательство с нулевым разглашением - Пример23 января 2011Оглавление: 1. Доказательство с нулевым разглашением 2. Общая структура доказательств с нулевым разглашением 3. Пример 4. Злоупотребления Назовем проверяющую сторону Петей, а доказывающую сторону Димой. Допустим Диме известен Гамильтонов цикл в большом графе G. Пете известен граф G, но он не знает гамильтонова цикла в нём. Дима хочет доказать Пете, что он знает гамильтонов цикл, не выдавая при этом ни самого цикла, ни какой-либо информации о нём. Для этого Петя и Дима совместно выполняют несколько раундов протокола:
В каждом раунде Петя выбирает новый случайный бит, который неизвестен Диме, поэтому чтобы Дима мог ответить на оба вопроса, нужно чтобы H был в самом деле изоморфен G и Дима должен знать гамильтонов цикл в H. Поэтому после достаточного числа раундов, Петя может быть уверен в том, что у Димы действительно есть гамильтонов цикл в G. С другой стороны, Дима не раскрывает никакой информации о гамильтоновом цикле в G. Более того, Пете сложно будет доказать кому-либо ещё, что он сам или Дима знает гамильтонов цикл в G. Предположим, что у Димы нет гамильтонова цикла в G и он хочет обмануть Петю. Тогда Диме необходим неизоморфный G граф G' , в котором он всё-таки знает гамильтонов цикл. В каждом раунде он может передавать Пете либо H' изоморфный G' , либо H изоморфный G. Если Петя попросит доказать изоморфизм и был передан H, то обман не вскроется. Аналогично, если он просит показать гамильтонов цикл и был передан H' . В таком случае вероятность того, что Дима все-таки обманет Петю после n раундов, равна 1/2, что может быть меньше любой заранее заданной величы при достаточном числе раундов. Предположим, что Петя не узнал гамильтонов цикл, но хочет доказать Васе, что Дима его знает. Если Петя, например, заснял на видео все раунды протокола, Вася едва ли ему поверит. Вася может предположить, что Петя и Дима в сговоре и в каждом раунде Петя заранее сообщал Диме свой выбор случайного бита, чтобы Дима мог передавать ему H для проверок изоморфизма и H' для проверок гамильтонова цикла. Таким образом без участия Димы доказать, что он знает гамильтонов цикл, можно лишь доказав, что во всех раундах протокола выбирались действительно случайные биты. Просмотров: 2915
|