Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
f{x) = y = gx{modN),
где N — большое нечетное составное число, а число д принадлежит группе %*N, имеющей большой простой порядок. Из этого следует, что
{gx{mcdN)\xe<l>(N)}cZ*N,
т.е. количество элементов в этом подмножестве меньше, чем 4>{N).
Предположим, что доказывающая сторона, Алиса, знает разложение числа N на простые множители. (Напомним, что в разделе 18.3.3 мы предполагали, что Алиса не знает факторизации числа N, а значит, протокол с нулевым разглашением является вычислительным.) Знание этого разложения позволяет Алисе провести идеальное доказательство с нулевым разглашением для у € {д).
Сформулируем вопрос следующим образом.
Можно ли улучшить эффективность протокола 18.1, увеличив размер оклика, генерируемого Бобом, как это сделано в протоколе идентификации Шнорра, если f(x) = gx(mod А^) и Алисе известно разложение составного целого числа N на простые множители?
Напомним, что, например, в протоколе идентификации Шнорра (протокол 18.2) мы немного увеличили длину оклика: Challenge е {0,1}1об21об2Р. в результате эффективность протокола повысилась: вместо т раундов, предусмотренных в протоколе 18.1, для доказательства оказалось достаточно выполнить log2^g2P раундов, причем вероятность противоречивости не изменилась.
К сожалению, если Алиса знает разложение числа N на простые множители, такой прием становится невозможным. Проблема заключается не в нулевом разглашении. Она связана с вероятностью противоречивости. Вероятность противоречивости данного протокола равна 6=1/2 независимо от длины оклика. Если вероятность противоречивости является постоянной и значительной, протокол должен быть логарифмическим. Гэлбрайт (Galbraith), Мао и Патерсон (Paterson) обнаружили этот факт в работе [117].
Для простоты изложения рассмотрим вероятность противоречивости однора-ундового трехшагового протокола, использующего длинный оклик (т.е., как показано в разделе 18.3.2, верификатор придерживается честной стратегии). Как будет
Глава 18. Протоколы с нулевым разглашением
709
показано ниже, этот полученный результат оказывается справедливым для любой длины оклика, превышающей один бит.
Итак, опишем протокол с нулевым разглашением и честной верификацией под названием "Непригодный протокол" (протокол 18.5), предназначенный для доказательства принадлежности элемента одной из подгрупп Щ^. Необходимо предупредить читателей, что этот протокол непригоден для использования ни в одном приложении. Мы описываем его лишь для демонстрации идеи.
Протокол 18.5. "Непригодный протокол"
ОБЩИЕ ВХОДНЫЕ ДАННЫЕ:
большое составное целое число;
д, у: два элемента группы Щ^, где д имеет большой порядок по модулю N,ay = gz(mod N).
ЗАКРЫТАЯ ИНФОРМАЦИЯ АЛИСЫ: целое число z < <?(АГ).
ЗАКЛЮЧЕНИЕ БОБА:
уЕ(д), т.е. у = gz(mod N) при некотором z.
1. Алиса генерирует число к е u^(n), вычисляет значение Commit *— gfe(mod N) и отсылает его Бобу.
2. Боб генерирует равномерно распределенную случайную величину Challenge < N и отсылает ее Алисе.
3. Алиса вычисляет значение Response <— к + z - Challenge(mod<?(AT)) и посылает его Бобу.
4. Если gResP°nse = Commit - yChallenge(mod AT), Боб принимает доказательство, в противном случае он его отвергает.
На первый взгляд, поскольку размер числа Challenge велик, Алисе нелегко его угадать, и она вынуждена точно следовать инструкциям протокола, что снижает вероятность непротиворечивости до величины 6 ss \/ф{И). Если бы это было правдой, то протокол состоял бы только из одного раунда. К сожалению, эта оценка вероятности противоречивости некорректна. Прием, позволяющий Алисе обмануть Боба, продемонстрирован в примере 18.4.
Пример 18.4. С этого момента будем обозначать доказывающую сторону как Алиса, поскольку она придерживается нечестной стратегии.
Зная факторизацию числа N, Алиса может легко вычислить нетривиальный квадратный корень единицы, т.е. элемент ? 6 Щ^, удовлетворяющий условиям ? Ф ±1 и ?2 = l(mod N). Вычисление квадратного корня выполняется с помощью алгоритма 6.5. Она может выбрать этот элемент так, что ? ^ (д).
710
Часть VI. Криптографические протоколы
Затем Алиса вычисляет общие входные данные:
Y <— ?<gz(mod АГ).
Очевидно, что Y €Е ?{<?), т.е. Y — это класс смежности подгруппы (д). Подчеркнем, что Y $ (д), поскольку ? ^ (д) (свойства класса смежности описываются теоремой 5.1. в разделе 5.2.1).
Вместо вычисления значения Commit по инструкциям протокола, Алиса подбрасывает монету Ь G t/{0,1}, пытаясь угадать четность оклика Боба. Затем она вычисляет величину Commit по следующей формуле.
„ . |gfe(modAr), если Ь = 0, Commit *— < ,
если 0=1.
В оставшейся части протокола Алиса должна следовать инструкциям.
Очевидно, что шансы правильно угадать число Challenge равны 1/2. Если Алиса правильно угадала четный оклик Challenge = 2и, Боб выполняет следую! щую верификацию.
Response = дкдг2и = Cowrn\t ¦ {?g)z2u = Commit • yChallen9e(moo1 ДГ)_
Следовательно, Боб принимает доказательство. Если Алиса правильно угадала нечетный оклик Challenge = 2и + 1, Боб выполняет верификацию следующим образом.
