Схема подписи с верификацией по запросу

В работах Д. Шаума (см., например, [Ка5,Ка14]) впервые была предложена схема подписи с верификацией по запросу, в которой абонент V

не может осуществить верификацию подписи без участия абонента S. Такие схемы могут эффективно использоваться в том случае, когда фирма - изготовитель поставляет потребителю некоторый информационный продукт (например, программное обеспечение) с проставленной на нем подписью указанного вида [КУ10]. Однако проверить эту подпись, которая гарантирует подлинность программы или отсутствие ее модификаций, можно только уплатив за нее. После факта оплаты фирма - изготовитель дает разрешение на верификацию корректности полученных программ.

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

Схема ПВЗ

Пусть каждый пользователь S

имеет один открытый ключ P и два секретных ключа S1 и S2. Ключ S1 всегда остается в секрете, - он необходим для генерации подписи. Ключ S2

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

Вместе с обозначениями секретного и открытого ключей xÎRZq и yÎRZ*p (взятых из отечественного стандарта на электронную цифровую подпись) введем также обозначения S1=x и S2=u, uÎRZq, а также открытый ключ P=(g,y,w), где wºgu(mod p). Открытый ключ P публикуется в открытом сертифицированном справочнике.

Протокол ГП

Подпись кода m вычисляется следующим образом. Выбирается kÎRZq и вычисляется

. Затем вычисляется sº[xr+mku](mod q). Пара (r,s) является подписью для кода m. Подпись считается корректной тогда и только тогда, когда

, где wºm-1(mod q).

Проверка подписи (с участием подписывающего) осуществляется посредством следующего интерактивного протокола.

Протокол верификации ПВ

Абонент V вычисляет

и просит абонента S доказать, что пара (r,s) есть его подпись под кодом m. Эта задача эквивалентна доказательству того, что дискретный логарифм g по основанию r равен (по модулю p) дискретному логарифму w по основанию g, то есть, что logg(p)wºlogr(p)g. Для этого:

Абонент V

выбирает a,bÎRZq, вычисляет

и посылает d абоненту S.

Абонент S выбирает tÎRZq, вычисляет

и посылает h1 и h2 абоненту V.

Абонент V высылает параметры a и b.

Если

, то абонент S

посылает V параметр t; в противном случае - останавливается.

Абонент V проверяет выполнение равенств

.

Если проверка завершена успешно, то подпись принимается как корректная.

Протокол ОП

В отвергающем протоколе S доказывает, что logg(p)w¹logr(p)g. Следующие шаги выполняются в цикле l раз.

Абонент V

выбирает d,eÎRZq, d¹1, bÎR{0,1}. Вычисляет

, если b=0 и

, если b=1. Посылает S значения a, b, d.

Абонент S

проверяет соотношение

. Если оно выполняется, то a=0, в противном случае a=1. Выбирает RÎRZq, вычисляет

и посылает V

значение c.

Абонент V

посылает абоненту S значение e.

Абонент S проверяет, что выполняются соотношения из следующих двух их пар:

. Если да, то посылает V значение R. Иначе останавливается.

Абонент V

проверяет, что

.

Если во всех l циклах проверка в п.5 выполнена успешно, то абонент V принимает доказательства.

Таблица 13.1. Протокол верификации является интерактивным протоколом доказательств с абсолютно нулевым разглашением.

Доказательство.

Требуется доказать, что вышеприведенный протокол удовлетворяет трем свойствам: полноты, корректности и нулевого разглашения [Ка5, Ка14].

Полнота означает, что если оба участника (V

и S) следуют протоколу и (r,s) - корректная подпись для сообщения m, то V примет доказательство с вероятностью близкой к 1. Из описания протокола верификации очевидно, что абонент S всегда может надлежащим образом ответить на запросы абонента V, то есть доказательство будет принято с вероятностью 1.

Корректность означает, что если V действует согласно протоколу, то какие действия не предпринимал бы S, он может обмануть V лишь с пренебрежимо малой вероятностью. Здесь под обманом понимается попытка S

доказать, что logg(p)wºlogr(p)g, когда на самом деле эти логарифмы не равны.

Предположим, что logg(p)w¹logr(p)g. Ясно, что для каждого a существует единственное значение b, то которое дает данный запрос d. Поэтому d не содержит в себе никакой информации об a. Если S смог бы найти h1, h2, t1

и t2 такие, что

,

где a1¹a2, то тогда выполнялось бы соотношение

logg(p)rº[(a1-a2)-1((b2-b1)+(t2-t1))](mod q)ºlogw(p)g.

Отсюда, очевидно, следует, что logg(p)wºlogr(p)g. В самом деле, пусть logw(p)gºlogg(p)r ºl. Тогда

,

что противоречит предположению. Следовательно, какие бы h1, h2, t1 и t2

не выбрал S, проверка, которую проводит V, может быть выполнена только для одного значения a. Отсюда вероятность обмана не превосходит 1/q. Отметим, что протокол верификации является безусловно стойким для абонента V, то есть доказательство корректности не зависит ни от каких предположений о вычислительной мощности доказывающего (S).

Свойство нулевого разглашения означает, что в результате выполнения протокола абонент V не получает никакой полезной для себя информации (например, о секретных ключах, используемых S).

Для доказательства нулевого разглашения необходимо для любого возможного проверяющего V* построить моделирующую машину

, которая является вероятностной машиной Тьюринга, работает за полиномиальное в среднем время и создает на выходе (без участия S) такое же распределение случайных величин, которое возникает у V* в результате выполнения протокола. В нашем случае, случайные величины, которые «видит» V*, - это h1, h2, и t. Необходимо доказать, что протокол верификации является доказательством с абсолютно нулевым разглашением, то есть моделирующая машина создает распределение случайных величин (h1,h2,t), которое в точности совпадает с их распределением, возникающим при выполнении протокола. Моделирующая машина

использует в своей работе V* в качестве «черного ящика».

Моделирующая машина

Запоминает состояние машины V*, то есть содержимое всех ее лент, внутреннее состояние и позиции головок на лентах. Затем получает от V*

значение d

и после этого снова запоминает состояние машины V*.

Выбирает hÎRZq и вычисляет

.

Получает от V* значения a и b. Если

, то

останавливается.

Машина

«отматывает» V*

на состояние, которое было запомнено в конце шага 1. Выбирает tÎRZq

и вычисляет

.

Машина

передает V*

h1, h2 и получает ответ (a¢,b¢). Возможны два варианта:

5.1. a=a¢, b=b¢. В этом случае моделирование закончено и

записывает на выходную ленту тройку (h1,h2,t) и останавливается.

5.2. a¹a¢ или b¹b¢. Отсюда следует, что

. Предположим, что b¹b¢. Из этого следует, что a¹a¢. Следовательно,

может вычислить

. Отсюда (b¢-b)/(a-a¢)=l - дискретный логарифм r по основанию g.

6. Машина

«отматывает» V*

на состояние, которое было заполнено в начале шага 1. Получает от V* значение d.

7. Выбирает hÎRZq вычисляет

и передает их V*.

8. Получает от V* значения a и b. Если

, то

останавливается.

В противном случае вычисляет

t=[h-al-b](mod q), выдает (h1,h2,t) на выходную ленту и останавливается.

К пп. 7 и 8 необходимо сделать следующее пояснение. Поскольку logg(p)wºlogr(p)g, из этого следует, что logw(p)gºlogg(p)r. Отсюда

.

Из описания моделирующей машины

очевидно, что она работает за полиномиальное время. Величины (h1,h2,t) на шаге 5.1 выбираются в точности как в протоколе и поэтому имеют такое же распределение вероятностей. Кроме того, значения (h1,h2), выбираемые на шаге 7, имеют такое же распределение, как и в протоколе. Чтобы показать что и t имеет одинаковое распределение, достаточно заметить, что машина V*

не может по h1 и h2 определить, с кем она имеет дело - с S или

. Поэтому, даже если бы V* могла каким-либо «хитрым» образом строить a и b с учетом (h1,h2), распределение вероятностей величин a

и b в обоих случаях одинаковы. Но значение t определяется однозначно четверкой величин a, b, h1, h2, при условии выполнения проверки на шаге 5 протокола. n

Таблица 13.2. Отвергающий протокол является протоколом доказательства с абсолютно нулевым разглашением.

Доказательство.

Полнота протокола очевидна. Если абоненты S

и V следуют протоколу, тогда абонент V всегда примет доказательства абонента S.

Для доказательства корректности прежде всего заметим, что если logg(p)wºlogr(p)g, то a и b, выбираемые абонентом V

на шаге 1, не несут в себе никакой информации о значении b. Поэтому, если S может “открыть” c, сгенерированное им на шаге 2, лишь единственным образом (то есть выдать на шаге 4 единственное значение R, соответствующее данному a), то проверка на шаге 5 будет выполнена с вероятностью 1/2 в одном цикле и с вероятностью 1/2l во всех l циклах.

Если же S может сгенерировать c таким образом, что с вероятностью, которая не является пренебрежимо малой, он может на шаге 4 “открыть” оба значения a, то есть найти R1 и R2 такие, что

, то алгоритм, который использует S для этой цели, можно использовать для вычисления дискретных логарифмов: loggd=R2-R1.

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

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

построить моделирующую машину

, которая создает на выходе (без участия S) такое же распределение случайных величин (в данном случае, c и R), какое возникает у V* в результате выполнения протокола.

Моделирующая машина

Следующие шаги выполняются в цикле l раз.

Машина

запоминает состояние машины V*.

Получает от V*

значения a, b и d.

Выбирает aÎR{0,1}, RÎRZq и вычисляет

. Посылает V* значение c.

Получает от V*

значение e.

Проверяет, было ли «угадано» на шаге 2 значение a (это значение было «угадано», если

и a=0, либо

и a=1). Если да, то записывает на входную ленту значение (c,R). В противном случае «отматывает» V* на то состояние, которое было запомнено на шаге 1, и переходит на шаг 2.

Легко видеть, что распределения случайных величин (c,R), возникающее в процессе выполнения протокола и создаваемые моделирующей машиной

, одинаковы, поскольку R в обоих случаях - чисто случайная величина, а величина c

записывается на выходную ленту машины

только тогда, когда a совпало с b.

Поскольку значение a выбирается машиной

на шаге 3 случайным образом, а c не дает V*

никакой информации о значении a, на каждой итерации a

будет угадано с вероятностью 1/2. Отсюда следует, что машина

работает за полиномиальное в среднем время. n

В работе [Ка14] показано, как строить схемы конвертируемой и селективно конвертируемой подписи с верификацией по запросу на основе отечественного стандарта ГОСТ Р 34.10-94. В таких схемах открытие определенного секретного параметра некоторой схемы подписи с верификацией по запросу позволяет трансформировать последнюю в обычную схему цифровой подписи.При этом открытие секретного параметра в конвертируемой схеме подписи с верификацией по запросу дает возможность верифицировать все имеющиеся и сгенерированные в дальнейшем подписи, в то время как в селективно конвертируемых схемах подписи с верификацией по запросу можно верифицировать лишь какую-либо одну подпись.

Содержание раздела