Неоспоримая подпись

Неоспоримая подпись — это схема цифровой подписи , которая позволяет подписывающему лицу выбирать, кому он разрешает проверять подписи. Схема добавляет явный отказ от подписи, предотвращая последующий отказ подписывающего лица проверить подпись из-за ее бездействия; ситуация, которая обесценила бы подпись в глазах проверяющего. Его изобрели Дэвид Чаум и Ханс ван Антверпен в 1989 году.

Обзор

В этой схеме подписывающая сторона, имеющая закрытый ключ, может опубликовать подпись сообщения. Однако подпись ничего не раскрывает получателю/проверяющему сообщение и подпись без участия в одном из двух интерактивных протоколов:

• Протокол подтверждения, который подтверждает, что кандидат является действительной подписью сообщения, выданного подписавшим, идентифицируемым открытым ключом.
• Протокол отклонения, который подтверждает, что кандидат не является действительной подписью сообщения, выданного подписавшим.

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

Важно, что обмены подтверждения и отклонения не подлежат передаче. Они достигают этого, обладая свойством нулевого знания; обе стороны могут создавать протоколы подтверждения и отказа, которые для третьей стороны неотличимы от правильных обменов.

Схема подписи назначенного проверяющего является улучшенной схемой отрицаемых подписей, позволяя для каждой подписи переносить интерактивную часть схемы на другую сторону, назначенного проверяющего, что снижает нагрузку на подписавшего.

Протокол с нулевым разглашением

Следующий протокол был предложен Дэвидом Чаумом .

группа G Выбирается , в которой задача дискретного логарифмирования неразрешима, и все операции схемы выполняются в этой группе. Обычно это конечная циклическая группа порядка p, содержащаяся в Z / n Z , где p — большое простое число ; эта группа оснащена групповой операцией целочисленного умножения по модулю n . произвольный примитивный элемент (или генератор) g из G Выбирается ; вычисленные степени g затем объединяются в соответствии с фиксированными аксиомами.

Алиса генерирует пару ключей, случайным образом выбирает закрытый ключ x , а затем получает и публикует открытый ключ y = g. ^х .

Подписание сообщений

1. Алиса подписывает сообщение m , вычисляя и публикуя подпись z = m. ^х .

Протокол подтверждения (т. е. признания)

Боб желает проверить подпись z m Алисы под ключом y .

1. Боб выбирает два случайных числа: a и b и использует их, чтобы скрыть сообщение, отправляя Алисе:

с = м ^а г ^б .

1. Алиса выбирает случайное число q , использует его для «скрытия» c , а затем подписывает его своим секретным ключом x и отправляет Бобу:

с ₁ = сг ^д и

с ₂ = с ₁ ^х .

Обратите внимание, что

с ₁ ^х = (cg ^д ) ^х = (м ^а г ^б ) ^х г ^qx = (м ^х ) ^а (г ^х ) ^б+к = г ^а и ^б+к .

1. Боб показывает a и b .
2. Алиса проверяет, что a и b являются правильными слепыми значениями, а затем, если это так, раскрывает q . Раскрытие этих блайндов делает обмен нулевым знанием.
3. Боб проверяет s ₁ = cg ^д , доказывая, что q не было выбрано нечестно, и

с ₂ = z ^а и ^б+к ,

доказательство того, что z является действительной подписью, выданной ключом Алисы. Обратите внимание, что

С ^а и ^б+к = (м ^х ) ^а (г ^х ) ^б+к .

Алиса может схитрить на шаге 2, попытавшись случайно угадать s ₂ .

Протокол отклонения

Алиса хочет убедить Боба, что z не является действительной подписью m под ключом g. ^х ; т. е. z ≠ м ^х . Алиса и Боб договорились о целом числе k , которое возлагает на Алису вычислительную нагрузку и вероятность того, что она случайно добьется успеха.

1. Боб выбирает случайные значения s ∈ {0, 1, ..., k} и a и отправляет:

v ₁ = м ^с г ^а и

v ₂ = z ^с и ^а ,

где возведение в степень с помощью a используется для скрытия отправленных значений. Обратите внимание, что

v ₂ = z ^с и ^а = (м ^х ) ^с (г ^х ) ^а = _v1 ^х .

1. Алиса, используя свой закрытый ключ, вычисляет v _1. ^х а затем частное,

v_v1 ^х в ₂ ⁻¹ = (м ^с г ^а ) ^х (С ^с г ^шах ) ⁻¹ = м ^сх С ^-с = (м ^х С ⁻¹ ) ^с .

Таким образом, v ₁ ^х в ₂ ⁻¹ = 1, если только z ≠ m ^х .

1. Затем Алиса тестирует версию _1. ^х в ₂ ⁻¹ для равенства значений:

(м ^х С ⁻¹ ) ^я для i ∈ {0, 1, …, k} ;

которые вычисляются путем многократного умножения m ^х С ⁻¹ (вместо возведения в степень для каждого i ). Если проверка успешна, Алиса предполагает, что соответствующий i равен s ; в противном случае она предполагает случайное значение. где г = м ^х , (м ^х С ⁻¹ ) ^я = _v1 ^х в ₂ ⁻¹ = 1 для всех i , s невосстановимо.

1. Алиса фиксирует i : она выбирает случайное r и отправляет hash(r, i) Бобу.
2. Боб . показывает
3. Алиса подтверждает, что a — правильный слепой вариант (т. е. v ₁ и v ₂ с его помощью можно сгенерировать ), а затем, если это так, раскрывает r . Раскрытие этих блайндов делает обмен нулевым знанием.
4. Боб проверяет hash(r, i) = hash(r, s) , доказывая, что Алиса знает s , следовательно, z ≠ m ^х .

Если Алиса попытается обмануть на шаге 3, угадав s наугад, вероятность успеха равна 1/(k + 1) . Итак, если k = 1023 и протокол проводится десять раз, ее шансы составляют 1 к 2. ¹⁰⁰ .

См. также

• Неотказ от ответственности
• Назначенная подпись проверяющего
• Темы криптографии