Проблема дискретного логарифма

Существует большое простое число p и генератор g. Алиса хочет для конкретного x найти такое e, для которого

g^eº x(mod p)

Это трудная проблема, и Алисе не хватает вычислительных мощностей для вычисления результата. У Боба есть такие возможности - он представляет правительство, или мощный вычислительный центр, или еще какую-нибудь влиятельную организацию. Вот как Алиса может получить помощь Боба, не раскрыв ему x[547, 4]:

(1) Алиса выбирает случайное число r, меньшее p.

(2) Алиса вычисляет

x'= xg^rmod p

(3) Алиса просит Боба решить

g^e'º x'(mod p)

(4) Боб вычисляет e' и посылает его Алисе.

(5) Алиса восстанавливает e, вычисляя

e= (e' - r) mod (p - 1)

Аналогичные протоколы для проблем квадратичных остатков и примитивных корней приведены в [3, 4]. (См. также раздел 4.8.)

Бросание "честной" монеты

Следующие протоколы позволяют Алисе и Бобу бросать честную монету в сети передачи данных (см. раздел 4.9) [194]. Это пример бросания монеты в колодец (см. раздел 4.10). Сначала только Боб узнает результат броска и сообщает его Алисе. Затем Алиса может проверить, что Боб сообщил правильный результат броска.

Бросание "честной" монеты с помощью квадратных корней

Подпротокол бросания честной монеты:

(1) Алиса выбирает два больших простых числа, pи q, и посылает их произведение nБобу.

(2) Боб выбирает случайное положительное целое число r, меньшее n/2. Боб вычисляет

z = r²mod n

и посылает z Алисе.

(3) Алиса вычисляет четыре квадратных корня z(mod n). Она может сделать это, так как она знает разложение n на множители. Назовем их +x, -x, +y и -y. Обозначим как x' меньшее из следующих двух чисел:

xmod n

-xmod n

Аналогично, обозначим как y' меньшее из следующих двух чисел:

ymod n

-ymod n

Обратите внимание, что r равно либо x',либо y'.

(4) Алиса делает пытается угадать, какое из значений равно r - x' или y', и посылает свою догадку Бобу.

(5) Если догадка Алисы правильна, результатом броска монеты является "орел", а если неправильна - "решка". Боб объявляет результат броска монеты.

Подпротокол проверки:

(6) Алиса посылает pи q Бобу.

(7) Боб вычисляет x' и y' и посылает их Алисе.

(8) Алиса вычисляет r.

У Алисы нет возможности узнать r, поэтому она действительно угадывает. Она на этапе (4) сообщает Бобу только один бит своей догадки, не давая Бобу получить и x', и y'. Если Боб получит оба этих числа, он сможет изменить rпосле этапа (4).

Бросание "честной" монеты с помощью возведения в степень по модулю p

В этом протоколе в качестве однонаправленной функции используется возведение в степень по модулю простого числа p [1306]:

Подпротокол бросания честной монеты:

(1) Алиса выбирает простое число p так, чтобы множители p-1 были известны, и среди них было по крайней мере одно большое простое число.

(2) Боб выбирает два примитивных элемента, hи t, в GF(p). Он посылает их Алисе.

(3) Алиса убеждается, что hи tявляются примитивными элементами, и затем выбирает случайное число x, взаимно простое с p-1. Затем она вычисляет одно из двух значений:

y= h^xmod p, или y= t^xmod p

Она посылает yБобу.

(4) Боб пытается угадать, вычислила Алиса yкак функцию h или как функцию t, и посылает свое предположение Алисе.

(5) Если догадка Боба правильна, результатом бросания монеты является "орел", в противном случае - "решка". Алиса объявляет результат броска монеты.

Подпротокол проверки:

(6) Алиса раскрывает Бобу значение x. Боб вычисляет h^xmod p и t^xmod p, убеждаясь, что Алиса играла честно и проверяя результат броска. Он также проверяет, что x и p-1 - взаимно простые числа.

Чтобы Алиса могла смошенничать, она должна знать два целых числа, xи x', для которых выполняется h^xºt^x' mod p. Для того, чтобы узнать эти значения, ей нужно вычислить:

log_th =x'x^-1mod p-1 и log_th =xx'^-1mod p-1.

Это трудные проблемы.

Алиса смогла бы сделать это, если бы она знала log_th, но Боб выбирает hи tна этапе (2). У Алисы нет другого способа кроме, как попытаться вычислить дискретный логарифм. Алиса может также попытаться смошенничать, выбрав x, которое не является взаимно простым с p-1, но Боб обнаружит это на этапе (6).

Боб может смошенничать, если hи tне являются примитивными элементами в поле in GF(p), но Алиса сможет легко проверить это после этапа (2), так как ей известно разложение p-1 на простые множители.

Удачным в этом протоколе является то, что если Алиса и Боб захотят бросить несколько монет, он7и смогут использовать одни и те же значения p, h и t. Алиса просто генерирует новое x, и протокол продолжается с этапа (3).

Бросание "честной" монеты с помощью целых чисел Блюма

В протоколе бросания монеты можно использовать челые числа Блюма.

(1) Алиса генерирует целое число Блюма n, случайное x, взаимно простое с n, x₀= x²mod n и x₁= x₀²mod n. Она посылает Бобу n и x₁.

(2) Боб угадывает, четным или нечетным является x₀.

(3) Алиса посылает x Бобу.

(4) Боб проверяет, что nявляется целым числом Блюма (Алиса нужно передать Бобу множители nи доказательства того, что они являются простыми, или выполнить некоторый протокол с нулевым знанием, убеждающий Боба, что n- это целое число Блюма), и что x₀= x²mod n и x₁= x₀²mod n. Если все проверки выполняются, и Боб угадал правильно, он выигрывает бросок.

Это важно, чтобы nбыло числом Блюма. Иначе Алиса сможет найти такое x'₀, что x'₀²mod n = x₀²mod n=x₁, где x'₀ также является квадратичным остатком. Если бы x₀ был четным, а x'₀ - нечетным (или наоборот), Алиса могла бы мошенничать.