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