Научная литература
booksshare.net -> Добавить материал -> Криптография -> Венбо Мао -> "Современная криптография" -> 284

Современная криптография - Венбо Мао

Венбо Мао Современная криптография. Под редакцией Клюшиной Д.А. — М. : Издательский дом Вильямс, 2005. — 768 c.
ISBN 5-8459-0847-7
Скачать (прямая ссылка): sovremennaya_kriptografiya.djvu
Предыдущая << 1 .. 278 279 280 281 282 283 < 284 > 285 286 287 288 289 290 .. 311 >> Следующая

Пусть N — большое нечетное составное целое число, имеющее по крайней мере два простых нечетных множителя. В разделе 6.5 были рассмотрены квадратичные вычеты по модулю и установлены следующие факты из теории чисел Факт 1. Зная разложение числа N, с помощью алгоритма 6.5 для любого х\ Е QR/v можно эффективно вычислить квадратный корень у, удовлетворяющий условию у2 = a;(mocliV).
Факт 2. Для любого х Е QNR^y (квадратичного невычета) в группе "L*N не существует ни одного квадратного корня (шаг 1 в алгоритме 6.5 невыполним).
Факт 3. Если из условия х G QNR^ следует, что х • у Е QRjv, то у € QNR (читатели могут сами убедиться в этом, проверив все возможные варианты символов Якоби для чисел х, у и х ¦ у). Используя эти факты, можно создать идеальный протокол доказсипельс
с нулевым разглашением, позволяющий Алисе доказать Бобу, что заданное 4HCJ
является квадратичным вычетом по нечетному составному модулю. Этот протоке
разработали Голдвассер, Микали и Раков [126].
Непротиворечивость
Предположим, что х Е QNRjy (т.е. Алиса жульничает). Оценим вероятность противоречивости 6. Разумеется, будем предполагать, что Алиса обладает неограниченными вычислительными ресурсами.
Глава 18. Протоколы с нулевым разглашением
699
Протокол 183. Протокол доказательства с нулевым разглашением принадлежности числа множеству квадратичных вычетов
ОБЩИЕ ВХОДНЫЕ ДАННЫЕ:
N: большое нечетное составное число, не являющееся степенью простого числа.
х\ элемент множества QR/y. ЗАКРЫТЫЕ ВХОДНЫЕ ДАННЫЕ АЛИСЫ:
у G TL*N : у2 = ж (mod А7'). ЗАКЛЮЧЕНИЕ БОБА:
х е QRN.
Следующие шаги выполняются тп раз.
1. Алиса генерирует число и € t/QR./v> вычисляет значение Commit <— и2 (mod N) и посылает его Бобу.
2. Боб генерирует число Challenge € ry{0,1} и посылает его Алисе.
{и, если Challenge = О,
uy(modN), если Challenge = 1,
и посылает его Бобу. 4. Боб проверяет значение
Response (mod А7} =
{Commit, если Оклик = О,
Commit X(modN), если Оклик = 1.
Если проверка завершается неудачно, Боб посылает отказ и прекращает работу протокола.
Боб принимает доказательство.
Если Challenge = 0, Боб видит, что число Response является квадратным корнем передаваемого числа, т.е. Commit G qrn.
Если Challenge = 1, Боб видит, что число Response является квадратным корнем числа Commit ¦ х, т.е. Commit ¦ х € QRjy. Из факта 3 следует, что в этом случае Commit € QNR^.
Итак, если х е QNRjy, Боб видит, что Commit G QR^ или Commit € QNRjy в зависимости от того, какой случайный бит оклика он посылает Алисе: 0 или 1. Поскольку Алиса послала число Commit до того, как Боб извлек случайный бит оклика, она должна была правильно предугадать этот бит. Очевидно, что в этом случае вероятность ошибки равна 8 = 1/2. Поскольку Боб выполняет верификацию тп раз, вероятность противоречивости протокола равна 2~т.
700
Часть VI. Криптографические протоколы
Непротиворечивость протокола выполняется благодаря факту 2, вследствие которого даже Алиса, обладающая неограниченными вычислительными ресурсами, не может вычислить квадратный корень числа хЕ QNR^ и угадать случайный бит оклика.
Полнота и идеальность нулевого разглашения
Полнота протокола непосредственно следует из факта 1. Идеальность протокола можно продемонстрировать, сконструировав алгоритм уравнивания ?Q, генерирующий стенограмму доказательства.
1. Алгоритм ?Q генерирует число Response^ € иЩя-
2. Алгоритм ?Q генерирует число Challenge, ? [/{0,1}.
3. Алгоритм ?Q вычисляет
Легко проверить, что элементы поддельной и подлинной стенограмм имеют одинаковое распределение.
18.4.2.2 Доказательство принадлежности числа множеству
Используя идеи, лежащие в основе протокола 18.3, можно создать протокол доказательства с нулевым разглашением принадлежности числа множеству квадратичных невычетов. Основная идея заключается в следующем.
При общих входных данных х Е QNRjy Боб может послать Алисе случайный) оклик, используя формулы Challenge <— r2(mod А'") или Challenge' <— a;r2(raod А'"), где г — случайный элемент группы "L*N. Очевидно, что Challenge eQR/v, и Алиса, проверив это, может ответить ДА. С другой стороны, если число х действительно принадлежит множеству QNRjy, то по факту 3 Challenge' € QNRjy. В этом случае Алиса также видит это и отвечает НЕТ.
Многократно посылая Алисе случайные оклики то из множества QR/v, то из множества QNRjy, Боб может проверить факт х Е QNRjy, ориентируясь на правильные ответы Алисы. Подробное описание этого протокола приведено в работе [126].
Доказательства с нулевым разглашением принадлежности числа множеству квадратичных вычетов или невычетов позволяют проверить корректность шифрования произвольной битовой строки в схеме вероятностного шифрования Голд-вассера-Микали (алгоритм 14.1). Кроме того, из них следует важный теоретический результат, изложенный в разделе 18.2.3.
Response2 (mod А^), если Challenge = 0, Response2/a;(mod А'"), если Challenge = 1.
квадратичных невычетов
Глава 18. Протоколы с нулевым разглашением
701
18.5 Протоколы с двусторонней ошибкой
Во всех протоколах с нулевым разглашением (доказательства или аргументации), изученных нами до сих пор, вероятность полноты (18.2.2) всегда оценивалась величиной е = 1, а вероятность противоречивости всегда была ненулевой — 8 > 0. Если е = 1, то протокол является абсолютно полным, т.е., если доказывающая сторона не жульничает, верификатор всегда принимает доказательство. Используя терминологию, введенную для описания ошибок в рандомизированных алгоритмах (раздел 4.4), можно сказать, что все эти протоколы имеют одностороннюю ошибку (one-sided error) и принадлежат подклассу Монте-Карло (т.е. "всегда высокочувствительные и, вероятно, точные", см. раздел 4.4.3). В таких протоколах односторонняя ошибка может совершаться Алисой, т.е. Алиса может жульничать и пытаться "доказать", что х е l, хотя на самом деле х ? l, а обманутый Боб может принять это "доказательство" (хотя вероятность противоречивости 8 может сделать сколь угодно малой, независимо повторяя процесс доказательства).
Предыдущая << 1 .. 278 279 280 281 282 283 < 284 > 285 286 287 288 289 290 .. 311 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed