Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Передача с секретом — это специальное сообщение, которое Алиса создает с помощью открытого ключа Боба, т.е. предназначенного верификатора. Обозначим передачу с секретом, созданную с помощью открытого ключа Боба ув, как
ТС(ад, г, ув).
Здесь w — передаваемое значение, а т — случайное число. Укажем два важных свойства передачи с секретом.
Фраза "доказательство знания" всегда заключается в кавычки, поскольку, строго говоря, эвристический метод Фиата-Шамира позволяет проводить лишь аргументацию (см. раздел 18.4.1).
718
Часть VI. Криптографические протоколы'
Свойство 18.1 (Свойства передачи с секретом).
1. Без секретного компонента ключа у в передача является связанной, т.е. на существует эффективного алгоритма вычисления коллизии w\ ф w2, удо-1 влетворяющей условию JC(w\,г,ув) = TC(w\, г7, ув)-
2. Используя закрытый компонент ключа ув, легко вычислить любое количе! ство коллизий.
Пример 18.5 (Схема на основе передачи с секретом.). Пусть (р, q, д) — числа из общих входных данных протокола идентификации Шнорра, аув = gXB(modp) — открытый ключ Боба, где Хъ €Е TLq.
Если Алиса желает скрыть число wE'Lq, она генерирует число r€[/Z9 и вычис-1 ляет передачу с секретом ТС(ад, г, у в) *— gwyB(modp). Она может открыть значе^ ние TC(w, г, у в), раскрыв пару (w, г). Проверим свойства передачи TC(w, г, ув)\
Во-первых, не зная закрытый ключ Боба хв, Алиса может раскрыть передачу только с помощью пары (w, г). Предположим противное, т.е. что она знает другуш пару (и/, г'), позволяющую раскрыть передачу, где vJ ф w(modq) (поскольку г' ф r(mod q)). Тогда, поскольку
l = gw-w"yB-r'(mcdp), I
получаем
ti/—ги
ув = дхв =¦ д-^ (modp),
т.е. Алиса знает число хв=WT,~2^ (mod q). Это противоречит предположению о том! что Алиса не знает числа хв-
Во-вторых, используя ключ хв, Боб может сгенерировать числа u,<t,w2, r\ € i/Z9, где w' ф w{m.odq). Затем он вычисляет параметр
w\ — W2 + г\Хв г2 <--.
хв
Легко убедиться, что ТС(™1} гу, ув) = 1С{ъи2, г2, ув)-
В разделе 18.3.2.2 показано, что "доказательство знания", проведенное с помощью эвристического метода Фиата-Шамира, представляет собой тройку (CommitJ Challenge, Response), построенную доказывающей стороной, т.е. Алисой. В этой тройке компонент Commit содержит число к, которое, зафиксировав, Алиса больше не может изменить.
В схеме NIZK, предложенной Якобсоном и его соавторами, доказательство представляет собой кортеж
(w, г, Commit, Challenge, Response). (18.7.1)
Глава 18. Протоколы с нулевым разглашением
719
Здесь пара (гу,г) представляет собой открытую информацию, предназначенную для создания сообщения ТС(гу, г, ув)- Эта пара добавляется для того, чтобы предназначенный верификатор Боб мог использовать секретную информацию для поиска коллизий и моделирования доказательства Алисы.
Создание доказательства
Алиса создает доказательство (18.7.1) следующим образом. Р.1. Алиса генерирует числа w, г ? иЪя и вычисляет передачу ТС(ад, г, у в) <— gwyrB{moup).
Р.2. Число Commit вычисляется так же, как и в эвристическом методе Фиата-Шамира: генерируя число к^иЪя и вычисляя значение Commit *— gk(modp).
Р.З. Число Challenge генерируется, как обычно: с помощью функции хэширования (применяемой к необязательному сообщению М).
Challenge <— h(JC(w, г, ув) || Commit || [М]).
Р.4. Для вычисления значения Response также используется число ги.
Response <— к + xa(Challenge + w)(modq).
Верификация доказательства
Получив кортеж доказательства (18.7.1) (и необязательное сообщение М), Боб выполняет его проверку, используя следующую процедуру. VI. Вычислить Challenge <— h(JC(w, г, ув) || Commit || [М]).
V.2. Проверить условие gResP°nse = Commit yAbaiie"9eyA!(modp). Если условие выполняется, доказательство принимается, в противном случае оно отклоняется. Докажем стойкость этой схемы.
18.7.1.1 Стойкость Полнота
Доказательство Алисы (18.7.1) очень похоже на кортеж (Commit, Challenge, Response), создаваемый в эвристическом методе Фиата-Шамира. Единственный элемент, который отличает это доказательство,—дополнительное число уд (mod р). Это число умножается на правую часть выражения, проверяемого на этапе верификации (шаг V.2). Таким образом, эта схема является полной.
Непротиворечивость
Число (mod р), известное предназначенному верификатору, является фиксированным, поскольку значение w в сообщении ТС(ад, г, ув) фиксировано. Следовательно, учитывая первое свойство передачи с секретом, Алиса не может изменить число у^(modр), не зная ключа Боба хВ- Таким образом, если Боб уверен,
720
Часть VI. Криптографические протоколы
что его закрытый ключ Алисе не известен, то множитель y^(modp) является константой, а значит, тройка (Commit, Challenge, Response) — это подлинный кортеж, созданный Алисой с помощью эвристического метода Фиата-Шамира. Итак, непротиворечивость этой схемы зависит от непротиворечивости доказательства по методу Фиата-Шамира. Следует заметить, что, поскольку вычислительные ресурсы Алисы полиномиально ограничены (чтобы предотвратить инвертирование функции хэширования или открытого ключа Боба), эту схему следует считать аргументацией, а не доказательством.
