Теория и практика защиты программ


         

Требуется доказать, что вышеприведенный протокол


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

Требуется доказать, что вышеприведенный протокол удовлетворяет трем свойствам: полноты, корректности и нулевого разглашения [Ка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).

Содержание  Назад  Вперед