Научная литература
booksshare.net -> Добавить материал -> Криптография -> Венбо Мао -> "Современная криптография" -> 279

Современная криптография - Венбо Мао

Венбо Мао Современная криптография. Под редакцией Клюшиной Д.А. — М. : Издательский дом Вильямс, 2005. — 768 c.
ISBN 5-8459-0847-7
Скачать (прямая ссылка): sovremennaya_kriptografiya.djvu
Предыдущая << 1 .. 273 274 275 276 277 278 < 279 > 280 281 282 283 284 285 .. 311 >> Следующая

Если проверка завершается неудачно, Боб посылает отказ и прекращает работу протокола.
Боб идентифицирует Алису.
(* Для вычисления величины gResponseyCha,lenge(modp) Боб должен применить алгоритм 15.2, эффективность которого эквивалентна одному возведению в степень по модулю. *)
правильного ответа по величине Commit • yChal,enae(modp) является угадывание числа Challenge перед фиксацией числа Commit.
1. Генерируем число Response € иЪд.
2. Угадываем значение Challenge € и{0, l}lo&2i°g2p.
3. Вычисляем величину Commit ^- pResP°nseyChallenge(modp).
Очевидно, что вероятность противоречивости при правильном угадывании на каждой итерации равна l/log2p, т.е. вероятность противоречивости протокола, состоящего из одного раунда, равна J = l/ log2 р.
Поскольку вероятность противоречивости протокола идентификации Шнорра, состоящего из одного раунда, меньше, чем у протокола 18.1, его эффективность
688
Часть VI. Криптографические протоколы
выше. Действительно, в протоколе 18.1 для снижения вероятности ошибки до* пренебрежимо малой величины S — 2~~т необходимо выполнить т итераций, в toi время как в протоколе идентификации Шнорра для этого достаточно ? = [og ^g р раундов.
При р » 21024 и т = 100 получаем, что ? = 100/10 = 10. Иначе говоря, увеличение длины оклика сокращает количество итераций по сравнению с протоколом 18.1 в 10 раз при той же самой вероятности противоречивости.
Идеальное нулевое разглашение
Для общих входных данных у можно построить уравнитель ?Q(y), время работы которого ограничено полиномом, зависящим от величины \р\.
1. Алгоритм ?Q инициализирует стенограмму Transcript в виде пустой строки.
2. For г = 1,2,..., log2 log2p
а) алгоритм ?Q генерирует число Response^ € u(g)i
б) алгоритм ?Q генерирует число Challengei € rj{0, 1}1о&21о&2Р;
в) алгоритм ?Q находит число Commit* <— gResponseiyChallenge'(modp);
г) Transcript *— Transcript || Commit*, Challenge^, Response^.
Очевидно, что строку Transcript можно создать за полиномиальное время, причем) ее элементы будут распределены точно так же, как элементы реальной стенограм J мы доказательства.
Анализ протокола идентификации Шнорра показывает, что увеличение размера оклика уменьшает количество итераций при той же самой вероятности проти-J воречивости. Остается неясным, почему размер оклика необходимо увеличить на такую странную и небольшую величину, как log2 log2 p.
Увеличение размера оклика не только повышает эффективность протокола (позитивный результат), но и имеет негативные последствия (см. раздел 18.3.2)1 Будьте внимательны, размер имеет значение!
18.3.2 Нулевое разглашение при честной верификации \
На первый взгляд, выбор величины |Challenge| = log2 log2p в протоколе идентификации Шнорра ничем не обоснован. Например, кажется, что, выбрав числи |Challenge| = log2 р, мы получили бы еще более эффективный протокол: для до! стижения той же самой вероятности противоречивости (<5 « 1 /р) понадобилась бы только одна итерация. Более того, уравнитель ?Q можно создать аналогич! но протоколу идентификации Шнорра. Такому уравнителю для создания строки Transcript, состоящей из равномерно распределенных случайных величин, пона" добилась бы только одна итерация.
Однако сделать это довольно трудно. Попробуем разобраться в причинах.
Глава 18. Протоколы с нулевым разглашением
U07
18.3.2.1 Как действует нечестный верификатор
Предположим, что Боб — нечестный верификатор (dishonest verifier), т.е. он не следует протокольным инструкциям и постоянно пытается заставить Алису раскрыть дополнительную информацию. Предположим, что Боб может сгенерировать такое большое число Challenge, что число 2Challenge является неполиномиально ограниченной величиной. Тогда Боб может изобрести трюк, заставляющий Алису создать неправильную стенограмму, которую невозможно приравнять или подделать за полиномиальное время. Если Боб может сделать это, то по определению 18.3.1.1 протокол не может быть длиннее идеального протокола с нулевым разглашением.
Рассмотрим немного измененный протокол идентификации Шнорра, позволяющий Бобу выбирать число Challenge ? Zg, т.е. расширять пространство окликов с {0,1}1о&21ое2р до всей группы Ъч. Вот какие действия должен выполнить Боб, реализуя модифицированный протокол идентификации Шнорра.
Получив число Commit, он применяет подходящую псевдослучайную функцию prf с достаточно большим пространством значений Zg и вычисляет значение по следующей формуле.
Challenge <— prf ("Осмысленное сообщение, подписанное Алисой || Commit").
Величина Challenge, созданная таким образом, является псевдослучайной. Смысл предложения "Осмысленное сообщение, подписанное Алисой" будет разъяснен позднее.
Бедная Алиса, неспособная отличить случайные величины от псевдослучайных (предположение 4.2), не понимает, что число Challenge является псевдослучайным, и продолжает выполнять протокол, посылая обратно величину Response «— к + а - Challenge(modp).
Напомним, что ответ Алисы удовлетворяет условию
Commit = ffResponseyChal,en9e(modp), (18.3.1)
поскольку именно эту операцию выполняет Боб на этапе верификации. Следовательно, Алиса помогает Бобу создать следующее уравнение.
Предыдущая << 1 .. 273 274 275 276 277 278 < 279 > 280 281 282 283 284 285 .. 311 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed