Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Идеальное нулевое разглашение
Поскольку Бобу известна секретная информация хв, с точки зрения любого постороннего наблюдателя, множитель y^(modp) больше не является константой. Наоборот, это число является объектом для манипуляций Боба. Действительно, поскольку Боб может свободно имитировать сообщение ТС(гу, г, ув), кортеж (18.7.1) можно точно сымитировать.
Процедура имитации
Боб генерирует числа Response, а,(3? u%q и выполняет следующие операции.
5.1. TC(w,r,yB) <-sa(modp).
5.2. Commit ^e^y^modp).
5.3. Challenge h(JC(w,r,yB) || Commit || [M]).
5.4. w <— /3 — Challenge(modQ).
5.5. r «— (a — w)/xB(n\odq).
5.6. Вывод кортежа (w, r, Commit, Challenge, Response).
Покажем, что эта имитация доказательства является идеальной Во-первых, из выражения на шаге S.2, получаем, что
^Response = CommJt ^(modp).
Из шага V.3 следует, что
Commit у°А = Commity™+Challenge = Commit ^"^^(modp).
Итак,
Response _ CommJt y^^{lnodp)i
что полностью соответствует этапу верификации V.2. Во-вторых, из шага S.5, следует, что
gwyrB = gw+rXB^ga(modp).
Глава 18. Протоколы с нулевым разглашением
721
Проверяя конструкцию ТС(го, г, ув), созданную на шаге S.1, легко убедиться, что секретная информация действительно имеет правильную структуру.
В заключение, нетрудно проверить, что, кроме правильной структуры, эти значения имеют требуемое распределение, генерируемое Алисой. Следовательно, алгоритм имитации, выполняемый Бобом, является алгоритмом уравнивания. Итак, мы доказали, что схема обладает идеальным нулевым разглашением.
18.7.1.2 Приложения
Якобсон и его соавторы предсказали интересные приложения своей схемы доказательства с предназначенным верификатором. Например, эту схему можно использовать в качестве альтернативы "неоспоримым подписям" (см. раздел 18.6.2.2): необязательное сообщение М можно рассматривать в качестве подписи Алисы, которую может верифицировать только предназначенный пользователь Боб. Рассмотрим ситуацию, в которой производитель программного обеспечения проверяет происхождение своей продукции. Если производитель Алиса использует "доказательство с предназначенным верификатором", то покупатель Боб не может убедить третью сторону в законном происхождении продукции, поскольку он может имитировать это доказательство.
Другим приложением является электронное голосование. Получив голос Кэрол, центр голосования должен послать ей подтверждение, сообщающее, что ее голос учтен. Очень важно, чтобы центр мог убедить Кэрол в правильности своего доказательства, предотвратив вмешательство Злоумышленника, стремящегося исказить результаты голосования. Если подтверждение создано с помощью "доказательства с предназначенным верификатором", то Злоумышленник не может проверить его корректность. Очевидно, что Кэрол может точно имитировать подтверждение своего голосования по отношению к любому кандидату по выбору Злоумышленника. Эта схема называется электронным голосованием со свободным подтверждением (receipt free electronic voting). Она изучена в работе Бенало (Benaloh) и Туинстра (Tuinstra) [30].
18.8 Резюме
В главе изучены протоколы с нулевым разглашением.
Сначала описаны интерактивные системы доказательства. Показано, что IP-протоколы тесно связаны с классом сложности MV, изученным в главе 4. Это позволило лучше понять задачи из класса NV. Как известно, для языка L € MV
задача I ё L является легкоразрешимой (соответственно трудноразрешимой), если существует (соответственно не существует) дополнительная информация, облегчающая работу алгоритма. Как показывает изучение главы, интуитивно ясно, что задача является легкоразрешимой (трудноразрешимой), если верификатор может (не может) работать совместно с доказывающей стороной.
722
Часть VI. Криптографические протоколы
Сформулировано несколько понятий нулевого разглашения: идеальное, с честным верификатором, вычислительное и статистическое. Продемонстрированы различия между доказательством и аргументацией, рассмотрены протоколы с двусторонними ошибками, исследована задача об эффективности раундов и в заключение изучены неинтерактивные протоколы с нулевым разглашением. Каждое ив понятий продемонстрировано на примере конкретного протокола. Надеемся, чтв< такое изложение было доступным для читателей и дало им достаточно полноц представление о протоколах с нулевым разглашением, которые предоставляют! своим пользователям скорее умозрительные, чем практические преимущества.
Протоколы с нулевым разглашением представляют собой активно разраба-1 тываемую область криптографии, связанную с компьютерными науками. Глава представляет собой всего лишь элементарное введение в этот предмет, поэтому* читатели, заинтересовавшиеся данной темой, должны обратиться к специальной научной литературе.
Упражнения
18.1. Объясните следующие понятия, связанные с ZK-протоколами.
а) Общие входные данные.
б) Закрытые входные данные.
в) Случайные входные данные.
г) Полнота.
д) Непротиворечивость.
е) Стенограмма доказательства.
ж) Нечестная доказывающая сторона.
з) Нечестный верификатор.
