Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[29]

(3)После того, как Пегги исчезнет в пещере, Виктор переходит в точку В.

(4)Виктор кричит Пегги, спрашивая ее либо о:

(a)или выйти из левого прохода

(b)выйти из правого прохода.

(5)Пегги исполняет его просьбу, при необходимости используя волшебные слова, чтобы отпереть дверь.

(6)Пегги и Виктор повторяют этапы (1) - (5) n раз.

Предположим, что у Виктора есть видеокамера, и он записывает все, что видит . Он записывает, как Пегги исчезает в пещере, записывает, как он сам кричит, указывая, где Пегги должна появиться, записывает как Пегги появляется. Он записывает все n тестов. Если он покажет эту видеозапись Кэрол, поверит ли она, что Пегги зн а-ет волшебные слова, отпирающие дверь? Нет. А что если Пегги и Виктор заранее договорились, что Виктор будет кричать, а Пегги будет делать вид, что она прошла весь путь. Тогда она будет каждый раз выходить из указанного Виктором места, не зная волшебных слов. Или они могли сделать по другому. Пегги входит в один из проходов и Виктор случайным образом выкрикивает свои просьбы . Если Виктор угадывает правильно, х о-рошо, если нет - они вырежут эту попытку из видеозаписи . В любом случае Виктор может получить видеозапись, показывающую в точности ту последовательность, которая получилась бы, если бы Пегги знала волше б-ные слова.

Этот опыт показывает две вещи. Во первых, Виктор не может убедить третью сторону в правильности док а-зательства. И во вторых, данный протокол является протоколом с нулевым знанием . Если Пегги не знает волшебных слов, то очевидно, что Виктор не узнает ничего из просмотра видеозаписи . Но так как нет способа отличить реальную видеозапись от подделанной, то Виктор не может ничего узнать из реального доказательства -это и есть нулевое знание .

Методика, используемая в этом протоколе, называется разрезать и выбрать из-за того, что она похож на классический протокол честного деления чего-либо :

(1)Алиса делит некую вещь пополам.

(2)Боб выбирает одну из половин себе.

(3)Алиса забирает оставшуюся половину.

В интересах Алисы честно разделить на этапе (1), потому что Боб выберет на этапе (2) ту половину, которая ему больше нравится. Майкл Рабин (Michael Rabin) первым использовал в криптографии технику "разрезать и выбрать" [1282]. Понятия интерактивного протокола и нулевого знания были формализованы позже [626,

Протокол "разрезать и выбрать" работает, потому что Пегги не может несколько раз подряд угадывать, отк уда Виктор попросит ее выйти. Если Пегги не знает секрета, он может выйти только из того прохода, в который она зашла. В каждом раундепротокола ее вероятность (иногда называемая аккредитацией) угадать, с какой стороны Виктор попросит ее выйти, составляет 50 процентов , поэтому ее вероятность обмануть Виктора также равна 50 процентам. Вероятность обмануть его в двух раундах составит 25 процентов , а во всех n раундах -один шанс из 2n. После 16 раундов у Пегги 1 шанс из 65536 обмануть Виктора. Виктор может уверенно предположить, что если все 16 доказательств Пегги правильны, то она действительно знает тайные слова, открыва ю-щие дверь между точками C и D. (Аналогия с пещерой несовершенна. Пегги может просто входить с одной стороны и выходить с другой, протокол "разрезать и выбрать" не нужен . Однако, он необходим с для нулевого знания с математической точки зрения.)

Предположим, что Пегги известна некоторая информация, которая является решением трудной проблемы . Базовый протокол нулевого знания состоит из нескольких раундов .

(1)Пегги использует свою информацию и случайное число для преобразования одной трудной проблемы в другую, изоморфную оригинальной проблеме. Затем она использует свою информацию и случайное число для решения новой трудной проблемы .

(2)Пегги вручает решение новой проблемы, используя схему вручения бита.

(3)Пегги раскрывает Виктору новый экземпляр проблемы. Виктор не может использовать эту новую пробл ему для получения информации о первоначальной проблеме или ее решении.

(4)Виктор просит Пегги либо

(a)доказать ему, что новая и старая проблема изоморфны (т.е., два различных решения для двух св я-занных проблем), либо

(b)открыть решение, полученное на этапе (2) и доказать, что это решение новой проблемы.


(5)Пегги исполняет его просьбу.

(6)Пегги и Виктор повторяют этапы (1) - (5) n раз.

Помните видеокамеру в протоколе для пещеры? Здесь вы можете сделать то же самое . Виктор может записать обмен между ним и Пегги. Он не сможет использовать эту запись для убеждения Кэрол, но он всегда м о-жет сговориться с Пегги с целью создать имитатор, который подделывает информацию Пегги . Этот аргумент может быть использован, чтобы доказать, что используется доказательство с нулевым знанием .

Математическая основа доказательства этого типа сложна. Проблемы и случайное преобразование должны выбираться осторожно, чтобы Виктор не получил никакой информации о решении оригинальной проблемы, даже после многих повторений протокола. Не все трудные проблемы можно использовать для доказательств с нулевым знанием, но большинство из них .

Изоморфизм графа

Объяснение этого понятия, пришедшего из теории графов [619, 622], может занять некоторое время. Граф представляет собой сеть линий ,соединяющих различные точки. Если два графа идентичны во всем, кроме имен точек, они называются изоморфными. Для очень больших графов доказательство их изоморфности может п о-требовать веков компьютерного времени, это одна из так называемых NP-полных проблем, рассматриваемых в разделе 11.1.

Предположим, что Пегги знает об изоморфности двух графов, Gl и G2. Следующий протокол докажет Виктору знание Пегги:

(1)Пегги случайным образом тасует Gl, получая другой граф, Н, который изоморфен Gl. Так как Пегги знает об изоморфизме Н и Gl, то ей также известен изоморфизм между Н и G2. Для любого другого поиск изоморфизма между Н и Gl или Н и G2 является такой же трудной задачей, как и поиск изоморфизма между Gl и G2.

(2)Пегги посылает Н Виктору.

(3)Виктор просит Пегги либо

(a)доказать, что Н и Gi изоморфны, либо

(b)доказать, что Н и G2 изоморфны.

(4)Пегги исполняет его просьбу. Она либо:

(a)доказывает, что Н и Gl изоморфны, не доказывая, что Н и G2 изоморфны, либо

(b)доказывает, что Н и G2 изоморфны, не доказывая, что Н и Gl изоморфны.

(5)Пегги и Виктор повторяют этапы (1) - (4) n раз.

Если Пегги не знает об изоморфизме между Gi и G2, она не сможет создать граф Н, изоморфный обоим графам. Она может создать либо граф, который изоморфен Gi, либо граф, который изоморфен G2. Как и в предыдущем примере у нее только 50 шансов из 100 угадать, какое доказательство потребует от нее Виктор на этапе

Этот протокол не дает Виктору никакой полезной информации, помогающей ему из ответов Пегги устан овить изоморфизм между Gi и G2. Так как Пегги для каждого нового раунда протокола генерирует новый граф Н, Виктор не сможет получить информацию независимо от того, из скольких раундов будет состоять их протокол . Он не сможет из ответов Пегги установить изоморфизм между Gi и G2.

В каждом раунде Виктор получает новое случайное преобразование Н, вместе с изоморфизмом между Н и Gl или G2. Виктор может также создать что-то подобное самостоятельно. Так как Виктор может создать имитацию протокола, это действительно доказательство с нулевым знанием .

Гамильтоновы циклы

Вариант этого примера был впервые представлен Мануэлем Блюмом (Manuel Blum) [196]. Пегги знает кружной, продолжительный путь вдоль линий графа, который проходит через каждую точку только один раз . Этот путь называется гамильтоновым циклом. Поиск гамильтонова цикла является другой тяжелой задачей . У Пегги есть эта информация - она, возможно, получила ее создав граф с конкретным гамильтоновым циклом -и она хочет доказать Виктору, что эта информация ей известна .

Пегги знает гамильтонов цикл графа, G. Виктору известен G, но не его гамильтонов цикл. Пегги хочет доказать Виктору, что она знает гамильтонов цикл, не раскрывая самого цикла . Вот как она должна действовать:

(1) Пегги случайным образом преобразовывает G. Она передвигает точки и изменяет их метки, создавая н о-


вый граф, H. Поскольку G и H топологически изоморфны (т.е., это один и тот же граф), если ей известен гамильтонов цикл G, то она легко может найти гамильтонов цикл H. Если она не сама создает H, определение изоморфизма между двумя графами будет являться другой сложной проблемой, решение которой также потребует веков компьютерного времени. Затем она шифрует H, получая H. (Должно использоваться вероятностное шифрование каждой строчки H, то есть, шифрованный 0 или шифрованная 1 для каждой линии H.)

(2)Пегги передает Виктору копию H.

(3)Виктор просит Пегги либо:

(a)доказать ему, что Н - это зашифрованная изоморфная копия G, либо

(b)показать ему гамильтонов цикл для Н.

(4)Пегги исполняет его просьбу. Она либо:

(a)доказывает, что Н - это зашифрованная изоморфная копия G, раскрывая преобразования и расши ф-ровывая все, не показывая гамильтонов цикл для G или Н, либо

(b)показывает гамильтонов цикл для Н, расшифровывая только те строки, которые образуют гамил ь-тонов цикл, не доказывая, что Н и G топологически изоморфны.

(5)Пегги и Виктор повторяют этапы (1) - (4) n раз.

Если Пегги не обманывает, она сможет предъявить Виктору одно из доказательств на этапе (3) . Однако, если гамильтонов цикл для G ей неизвестен, она не сможет создать зашифрованный граф H, который удовлетворяет обоим доказательствам. Лучшее, что она может сделать - это создать или граф, изоморфный G, или граф с таким же числом точек и линий и правильным гамильтоновым циклом . Хотя ее шансы угадать, какое доказательство потребует Виктор на этапе (3), составляют 50 процентов, Виктор может повторить протокол достаточное число раз, убеждаясь, что Пегги знает гамильтонов цикл для G.

Параллельные доказательства с нулевым знанием

В базовом протоколе с нулевым знанием используется n обменов информацией между Пегги и Виктором . Почему бы не выполнить их параллельно :

(1)Пегги использует свою информацию и n случайных чисел для преобразования трудной проблемы в n различных изоморфных проблем. Затем она с помощью своей информации и случайных чисел решает n новых трудных проблем.

(2)Пегги вручает решение n новых трудных проблем.

(3)Пегги раскрывает Виктору эти n новых трудных проблем. Виктор не может воспользоваться этими новыми проблемами для получения информации об оригинальных проблемах или их решении.

(4)Для каждой новой трудной проблемы Виктор просит Пегги либо

(a)доказать ему, что старая и новая проблемы изоморфны, либо

(b)раскрыть решение, врученное на этапе (2), и доказать, что оно является решением данной новой проблемы.

(5)Пегги исполняет его просьбу для каждой новой проблемы.

К несчастью, все не так просто. Этот протокол, в отличие от предыдущего, не обладает такими же свойств а-ми нулевого знания. На этапе (4) Виктор может потребовать, чтобы доказательство было представлено в виде значения однонаправленной хэш-функции всех значений, врученных на первом этапе, делая невозможным им и-тацию записи протокола. Это тоже нулевое знание, но другого рода . На практике оно представляется безопасным, но никто не знает, как это доказать . Мы действительно знаем только то, что при определенных условиях определенные протоколы для определенных проблем могут быть выполнены параллельно без потери свойства нулевого знания [247, 106, 546, 616].

Неинтерактивные доказательства с нулевым знанием

Кэрол невозможно убедить, потому что она не участвует в интерактивном процессе протокол. Для убеждения Кэрол и других заинтересованных лиц нам нужен неинтерактивный протокол .

Для неинтерактивных доказательств с нулевым знанием был придуман ряд протоколов [477, 198, 478, 197], которые не требуют непосредственного взаимодействия. Пегги может опубликовать их и, таким образом, док а-зать свое знание всем, у кого найдется время это проверить

Базовый протокол похож на параллельное доказательство с нулевым знанием, но место Виктора занимает



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203]