BC/NW 2012; №2 (21):11

BC/NW 2012; №2 (21):11.1

ЭФФЕКТИВНЫЕ НЕИНТЕРАКТИВНЫЕ ПРОТОКОЛЫ С НУЛЕВЫМ РАЗГЛАШЕНЕМ

Фролов А.Б.

Введение. Протоколы с нулевым разглашением секрета используются, как правило, в целях аутентификации, например, при сертификации открытых ключей, доказательстве подлинности электронной продукции, доказательстве корректности учета голоса избирателя на электронных выборах и в других защищенных компьютерных технологиях. Имеются два участника такого протокола - доказывающий P (prover) и проверяющий V (verifier). P знает некоторый секрет s и публикует открытый ключ (public key) - значение f(s), где f - односторонняя функция. Отвечая на вопросы проверяющего V, участник P должен доказать, что он действительно знает секрет s, соответствующий значению f(s), не разглашая ни одного бита информации об s. Известен ряд таких протоколов, например, протокол Шнорра доказательства знания дискретного логарифма (с функцией f возведения в степень в группе с трудной проблемой дискретного логарифма), протокол Фиата-Шамира доказательства знания квадратного корня (с функцией f возведения в квадрат в кольце , где m есть трудно факторизуемое произведение двух простых чисел), протокол доказательства знания разложения на множители большого составного числа и другие [1,2,3,4]. Такие протоколы имеют две вероятностные характеристики: вероятность e успешного прохождения протокола участником, действительно владеющим секретом (честным доказывающим P) - полнота (completeness) и вероятность d успешного прохождения протокола нечестным участником P’, не владеющим секретом, - некорректность (soundness). В упомянутых трех протоколах полнота e=1, а некорректность d=, где t это количество вопросов, заданных проверяющим V (или этапов доказательства). Вопросы проверяющего V требуют либо подтверждения знания секрета, либо подтверждения соблюдения протокола и выбираются им случайно. Честный доказывающий P имеет возможность правильно ответить на каждый такой вопрос, в то время как нечестный доказывающий P’, не зная заранее типа вопроса, вынужден выбирать один из двух возможных ответов наугад. При удачном угадывании типа вопроса он проходит данную проверку, при неудачном - нет. Первоначально эти протоколы были описаны как интерактивные протоколы, в каждой из t итераций которых доказывающий P выбирает сеансовый секрет, посылает связывающий его сеансовый открытый ключ (commit), проверяющий V посылает бинарный вопрос (challenge), на который доказывающий дает ответ (response). Предикат проверки имеет вид:

f(<response>)=<commit>×<public key>^<challenge>.

Открытие криптографического примитива передачи с забыванием (oblivious transfer) [5,6] позволило реализовать логику таких протоколов неинтерактивно [7]: доказывающий P посылает проверяющему V одновременно ответы на оба возможных вопроса, из которых V по своему усмотрению (на самом деле случайным образом) выбирает один. При этом P не знает, какой из ответов выберет V. Вопросы проверяющего V посылаются заранее в виде его открытых ключей. Таким образом эффект интерактивного протокола достигается в неинтерактивном режиме. Передача одного из двух сообщений с забыванием, реализуемая в таких протоколах, использует вероятностное шифрование, например, по схеме Эль Гамаля [8]. В работах [9,10] показано, что вследствие использования различных секретных ключей в двух или более сеансах вероятностного шифрования возможно многократное использование рандомизатора, чем достигается ускорение коммуникационной фазы протокола забывающей передачи. В настоящей работе идея повторного использования рандомизатора распространяется на последовательно исполняемые этапы протокола, чем достигается сокращение числа передаваемых элементов почти в 5t/(3t+1) раз, а для протоколов одноразового использования - в 4t/(2t+1) раз с почти квадратичным понижением некорректности.

Приведем описание известного базового протоколов и двух протоколов отражающих его логику, но обеспечивающих при тех же временных затратах существенное понижение некорректности и докажем безопасность предложенного упрощения базового протокола. Протоколы имеют установочную фазу согласования системных параметров, фазу инициализации, в которой выбирается секрет и через центр сертификации публикуется соответствующий открытый ключ доказывающего P, выбирается последовательность из t секретных ключей, соответствующая выбранной последовательности из t бинарных вопросов, и формируется последовательность соответствующих открытых ключей проверяющего V. Последняя передается в доверенный центр для проверки и опубликования. V получает от доверенного центра сертификации открытый ключ доказывающего P, а P - последовательность открытых ключей проверяющего V. На фазе коммуникации P формирует и пересылает проверяющему V t пар криптограмм ответов на оба вопроса данного этапа, из которых V по своему усмотрению (на самом деле случайно) выбирает и проверяет один. P не знает, какой из ответов выберет V. Доказательство принимается, при положительном итоге проверок на каждом из t этапов. Эта логика достигается посредством использования протокола передачи одного из двух сообщений с забыванием (1из 2 OT- протокола).

Системными параметрами неинтерактивного протокола доказательства знания дискретного логарифма являются: группа G с трудной проблемой дискретного логарифма, a - элемент группы высокого порядка, функция f возведения в степень в группе G при основании a, элемент UÎ{2,…, ord a-2}, с неизвестным обоим участникам дискретным логарифмом.

В фазе инициализации доказывающий P выбирает секрет sÎ{2,…, ord a-2}, формирует и публикует свой открытый ключ f(s)=a^s. Проверяющий V выбирает последовательность секретных ключей: где Î{1,2} - бинарные вопросы, {2,…, ord a-2}, формирует и отправляет в доверенный центр последовательность открытых ключей:

, .

Доверенный центр публикует ее после проверки: для всех j должно выполняться равенство Доказывающий P получает эту последовательность от доверенного центра.

В фазе коммуникации P выбирает последовательность секретных сеансовых ключей:

{2,…, ord a-2},

Он вычисляет и отправляет проверяющему V последовательность соответствующих открытых ключей:

().

Далее P выбирает случайным образом последовательность

различных рандомизаторов 2 ,…, ord a-2} и осуществляет последовательность ОТ-передач (передач с забыванием):

где

(,)=

= (,)

Проверяющий V получает последовательность ответов:

где элементы вычисляются следующим образом:

_V_{осуществляет последовательность проверок:}

Эффективный неинтерактивный протокол доказательства знания дискретного логарифма отличается от рассмотренного выше организацией ОТ-передач. После вычисления и отправления проверяющему V последовательности сеансовых открытых ключей доказывающий P выбирает случайным образом рандомизатор yÎ{2,…, ord a-2}, вычисляет и отправляет проверяющему V соответствующий элемент aи осуществляет последовательность ОТ-передач (передач с забыванием):

где

= (,)=

==(,).

С учетом ранее принятого элемента a эта последовательность может анализироваться проверяющим V как последовательность ОТ-передач

=(,)

Проверяющий V вычисляет последовательность ответов:

где элементы вычисляются следующим образом:

V осуществляет последовательность проверок (1).

Системными параметрами эффективного неинтерактивного протокола доказательства знания квадратного корня являются: трудно факторизуемое составное число m=pq, функция f возведения в квадрат в кольце , группа G с трудной проблемой дискретного логарифма, a - элемент группы высокого порядка, элемент UÎG с неизвестным обоим участникам дискретным логарифмом.

В фазе инициализации доказывающий P выбирает секрет , формирует и публикует свой открытый ключ f(s)= mod m.

Дальнейшее описание протокола отличается только видом сообщения

Сравним эффективность протоколов. При исполнении базового протокола от доказывающего P проверяющему V пересылаются 5t элементов группы G. При их вычислении доказывающий P выполняет 5t операций возведения в степень. Используя эффективные неинтерактивные протоколы передачи с забыванием одного из двух сообщений (1 из 2 NIEOT-протоколы [9,10]), количество передаваемых элементов и операций возведения в степень можно уменьшить до 4t. Наконец, использование единого рандомизатора y в каждом из t этапов доказательства позволяет понизить это число до 3t+1. Эффективными неинтерактивными протоколами с нулевым разглашением мы и называем протоколы, в которых используются единые для всех этапов проверки рандомизатор y и сеансовый ключ a системы вероятностного шифрования. Такие протоколы будем обозначать ENIZKnP-протоколы, а их традиционные прототипы будем обозначать NIZKnP-протоколы. Соответственно и обозначают некорректность таких протоколов. Протоколы однократного использования (single use) обозначаются ниже SUENIZKnP и SUNIZKnP. В таких протоколах передача от доказывающего P проверяющему V последовательности сеансовых открытых ключей осуществляется заранее и время их передачи в фазе коммуникации не учитывается и число передаваемых на этой фазе элементов равно 2t+1.

_{В итоге за время выполнения 3}_t_{этапов доказательства}_NIZKnP_{-протокола можно выполнить 5}_t_-_{1 этапов}_ENIZKnP_{-протокола, а за время выполнения 2}_t_{этапов доказательства}_SUNIZKnP_{-протокола можно выполнить 4}_t_-_{1 этапов}_SUENIZKnP_{-протокола, и обеспечить существенное
(для}_SU_{-протоколов почти
квадратичное) понижение некорректности:}

Докажем безопасность повторного использования рандомизатора при передачах с забыванием

Пусть вычислено сообщение . Чтобы вычислить , необходимо найти , то есть решить проблему Диффи - Хеллмана: при известных значениях a, ,найти = Знание вычисленного знания оказывается бесполезным: при вычислении

(4)

проверяющему V необходимо знать секретный рандомизатор y, известный только доказывающему P. Допустим, что удалось вычислить сообщение каким-то другим способом. Тогда удастся решить проблему Диффи-Хеллмана. Действительно, возьмем U=. Тогда из соотношения (4) найдем Тем самым решается проблема Диффи-Хеллмана: по известным вычисляется . Таким образом, доказано следующее

Утверждение. Проблема извлечения второго сообщения при повторном использовании рандомизатора в OT-протоколе и проблема
Диффи-Хеллмана эквивалентны.

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

Следствие 1. Использование единого рандомизатора на всех этапах неинтерактивного протокола доказательства с нулевым разглашением безопасно.

Следствие 2. Справедливы сравнения (2).

Прием повторного использования рандомизатора при разных секретных ключах проверяющего распространяется и на неинтерактиные протоколы доказательства с нулевым разглашением с предназначенным проверяющим [2,11]. Для понижения некорректности используют l секретных и соответствующих открытых , i=1,…,l ключей предназначенного проверяющего. Доказательство знания секрета представляется в виде последовательности из l наборов

(, Commit, Challenge Response), i=1,…,l.

Каждый элемент, кроме Challenge это элемент группы, в арифметике которой строится протокол, например, , длина записи такого элемента равна . Длина элемента Challenge равна . При этом общая длина доказательства равна l(4+ ).

Применение различных ключей проверяющего в каждой из этих последовательностей позволяет использовать в них одинаковые пары
()= (w,r) случайных элементов. Таким образом, доказательство можно построить из пары (w,r) элементов группы и l троек

(Commit, Challenge Response), i=1,…,l;

Здесь Commit =, где - случайное число,

Challenge =

Response =k+

(p,q,g) - системные параметры протокола Шнорра [2,12].

Проверка заключается вычислении l предикатов

, i=1,…, l.

Длина такого доказательства равна 2+l(2+ ). То есть она почти в два раза меньше длины стандартного доказательства. Таким образом, и в таких протоколах повторное использование рандомизатора влечет почти квадратичное понижение некорректности.

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

Работа выполнена при финансовой поддержке РФФИ,
проект №11-01-00792-а.

ЛИТЕРАТУРА

1. Введение в криптографию// Под ред. В.В.Ященко. - М. МЦНМО-Черо. 1998.

2. Венбо Мао. Современная криптография. Теория и практика. - М. Триумф, 2005.

3. Snorr C.P. Efficient identification and signatures for smart cards// Proc. Crypto’89. LNCS V. 435.1990. P. 239 -252.

4. Fiat A., Shamir A. How to prove yourself: practical solutions to identification and signature problem// Proc. Crypto 86. LNCS. V. 263. P. 186-194.

5. Rabin M.O. How to exchange secrets by oblivious transfer. Technical Report TR-81. Aiken Computation Laboratory. Harvard University. 1981.

6. Even S., Goldreich O., and Lemel A. A Randomized Protocol for Signing Contracts. Communications of the ACM, V. 28. Issue 6. 1985. P. 637−647.

7. Коблиц Н. Курс теории чисел и криптографии. - М. ТВП. 2001.

8. ElGamal T. A public-key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inform. Theory. IT-31(4). 1985. P. 469−472.

9. Фролов А.Б. Эффективные протоколы передачи комбинации сообщений с забыванием. Ползуновский вестник №2/1, 2012. C. 129-133.

10. Frolov А. Effective Oblivious Transfer Using Probabilistic Encryption\\ In Advances in Intelligent and Soft Computing. Springer. Verlag. 2012. (Accepted).

11. Jakobsson M., Sako K., and Impagliazzo. Designated verfier proof and their applications\\ In U.Mauer, editor, Advances in Cryptology - Proceedings of EUROCRYPT’96.LNCS 1070, Springer Verlag. 1996. P.143-154.

12. Schnorr C.P. Efficient identification and signature for smart cards\\ In G. Brassard, editor. Advances in Cryptology - Proceedings of EUROCRYPT’89. LNCS 435, Springer Verlag, 1990. P. 239-252.