ZK-протоколы

Криптографические протоколы

Несмотря на то что в основе построения ZK-протоколов лежат те же математические идеи, что и в протоколах , построенных на открытой криптографии, между ними есть некоторые отличия. Прежде всего они касаются:
- уменьшения эффективности в ходе использования. Протоколы доказательства с нулевым знанием не уменьшают свою эффективность даже при повторных передачах и соответственно являются стойкими к атаке с выборкой открытого текста. Данное свойство в некоторых случаях позволяет предпочесть использование ZK-протоколов;
- использования шифрования. Многие ZK-протоколы позволяют избегать употребления шифрования явным образом, что дает несомненные преимущества, например в случае экспортных ограничений;
- эффективности. Коммуникационная и вычислительная эффективность в ZK-протоколах основана прежде всего на том факте, что они по своей природе являются интерактивными протоколами доказательства.
Среди сходств данных протоколов можно отметить следующие:
- наличие недоказумых предположений. ZK-протоколы, так же как и протоколы , основанные на открытой криптографии, напрямую используют недоказуемые предположения (например, доказуемая стойкость к факторизации);
- доказуемость обладания свойством ZK. На практике достаточно сложно доказать наличие данного свойства у протокола.

Для практического рассмотрения концепции построения протоколов, обладающих свойством ZK, приведем оригинальную версию протокола Фиата и Шамира (Fiat-Shamir). Целью данного протокола является демонстрация знания секрета s доказывающей стороной, при этом информация о самом секрете не раскрывается проверяющему и он не имеет предварительно распределенных сведений. Безопасность протокола основана на сложности извлечения квадратного корня по модулю п (имеет то же значение, что и в RSA), не зная разложения п. Опишем общую структуру протоколов данного класса: А доказывает знание секрета s В при помощи t-шагов по три сообщения в каждом.
Параметры протокола: доверенный центр Т выбирает и публикует модуль n = pq (р и q сохраняются в секрете);
- каждый доказывающий выбирает секрет s взаимно простой с п, 1 < s < n - 1, Вычисляет v - s2mod n и регистрирует v у Т в качестве своего открытого ключа.
Сообщения, передаваемые в рамках каждого шага:
А-^В: х - r2mod n А<-В:ее {0,1} А^В:у - rsemodn
В принимает доказательство за t шагов, и последовательность действий в рамах протокола имеет следующий вид:
- А выбирает случайное число г, 1<г<п-1и посылает В х - r2mod n.
- В выбирает случайным образом е и посылает его А.
- А вычиляет у и посылает его В, где у - г (е = 0) или у = rs (е = 1).
- В отвергает доказательство, если у = 0, иначе производится проверка у2 = xv« m0(j n ]з зависимости от е у2 - х mod n или у2 = xv mod n, иначе v « s2 mod n.
Значение параметра t выбирается равным 20 или 40.
А-*В: начальные значения А*-В: запрос А-*В: ответ

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