Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Сначала Алиса и Боб договариваются о р и а точно так же, как и в предыдущем примере. Для того чтобы задаться некоторым битом Ь, Алиса случайным образом выбирает целое число у, лежащее на отрезке от 0 до р—2 и, кроме того, полагает 6 равным «-тому младшему значащему биту у. Затем она вычисляет блоб х = ау mod р и передает его Бобу. Ясно, что тогда свойства (а) и
(d), определяющие этот блоб, выполняются точно так же, как и в двух предыдущих реализациях битовых обязательств. Однако свойство (Ь) теперь справедливо безусловно, потому что а является генератором Ж*. Следовательно, дискретный логарифм х определяется однозначно, а это значит, что также однозначно задается и ы-тый младший значащий бит у. Наконец, свойство
(с) выполняется с вычислительной точки зрения при сделанном ранее криптографическом предположении, так как бит, закодированный блобом s, суть ни что иное, как hard(s).
В [78] были предложены некоторые другие схемы битовых обязательств. Существует также реализация, которая остается нераскрываемой, даже если и Алиса, и Боб имеют неограниченные вычислительные ресурсы, но она основывается на постулатах квантовой физики. Кроме того, еще одно применение является безусловно- нераскрываемым для всех сторон, которые взаимодействуют в многопользовательской среде (смотрите § 5) в предположении, что не более одной трети всех участников этого взаимодействия являются нечестными [111, 37].
§ 3. Доказательства с наименьшим раскрытием
(яалясало вместе с Клодом Крепеу и Дэвидом Чаумом)
Предположим, что Алиса хочет доказать, что ей известна некая информация. Например, это может быть какая-то теорема или разложение большого целого числа на простые множители. Предположим далее, что информация Алисы является проверяв-
Доказательства с наименьшим раскрытием 97
мой в том смысле, что существует эффективная процедура, способная подтвердить справедливость этой информации. Тогда, если Боб захочет проверить, что Алисе и в самом деле известна та информация, о знании которой она заявляет, то Алиса, для того чтобы убедить в этом Боба, может просто предоставить ему эту информацию, чтобы он сам смог выполнить проверяющую процедуру. Подобное доказательство было бы доказательством с наибольшим раскрытием, так Как в результате Бобу стала бы известна вся эта информация. Поэтому в дальнейшем он сам мог бы не только сообщать ее кому угодно, но даже утверждать, что она изначально являемся его собственной информацией.
В этом параграфе мы опишем общий и эффективный протокол для проведения доказательств с наименьшим раскрытием. Этот протокол позволяет Алисе убедить Боба после любого его разумного сомнения в том, что она действительно обладает некой информацией, которая с успехом пройдет проверяющую процедуру, но способ, которым она это делает, никоим образом не помогает ему определить саму эту информацию. Например, если такой информацией Алисы является доказательство какой-нибудь теоремы, то Боб будет в полной уверенности, что Алиса действительно знает, как ее доказывать, и, следовательно, что теорема верна. Однако Бобу при этом не предоставится никакого намека на то, как такое доказательство (за исключением разве что верхней границы на его длину) можно было бы осуществить ему самому. Следовательно, несмотря на то, что оригинальная информация Алисы является проверяемой, та убежденность в ее справедливости, которую получает Боб, фактически ничего ему не дает. В частности, проведение протокола с Алисой не обязано (а во многих случаях и не будет) предоставлять возможности Бобу впоследствии убедить в этом таким же образом кого-нибудь еще.
В общем случае это достигается с помощью интерактивного протокола, состоящего из нескольких раундов. В каждом раунде Бобу позволяется задавать Алисе один из двух возможных очень трудных вопросов. Эти вопросы задаются таким образом, что Алиса сможет ответить правильно на оба вопроса Боба лишь в том случае, если она действительно владеет тем секретом, о знании которого заявляет. Однако способ, которым Алиса это делает, не предоставляет Бобу никакой информации о сохраняемом
98 Применения
Глава 6
ею в секрете утверждении. Поскольку Алиса не может раньше времени предугадать, какой из вопросов задаст Боб, то каждый раунд протокола увеличивает его уверенность в справедливости ее секрета. В действительности она может надеяться обдурить его за к успешных раундов с экспоненциально уменьшающейся вероятностью 2~к. Мы будем называть такую технику приемом разрезания-и-выбора, поскольку каждый ее раунд подобен классическому «протоколу», с помощью которого двое детей делят кусок торта — один из них режет, а другой выбирает ту часть, которая ему больше нравится. Необычайная полезность приема «разрезания-и-выбора» состоит в том, что она обеспечивает экспоненциально возрастающую уверенность ценой лишь линейного увеличения числа раундов.
Самое раннее использование техники «разрезания-и-выбора», которое нам известно в связи с криптографическими интерактивными протоколами, было предложено Майклом Рабином в 1977 году [296]. Понятие интерактивного протокола было впоследствии формализовано, а Шафи Гольдвассер, Сильвио Микэли и Чарльзом Раковом в [199] было введено понятие нулевого знания. (Понятие нулевого знания сходно с понятием минимального раскрытия, за исключением того, что оно требует, чтобы Боб не мог получить из протокола вообще ничего, кроме знания о том, что Алиса обладает той информацией, о которой она заявляет.) Ласло Бабаи формализовал также понятие, сходное с понятием интерактивных протоколов [11]. Модели, представленные в [199, 11], предполагают, что доказывающий обладает неограниченными вычислительными ресурсами. Дэвидом Чаумом была предложена несколько иная модель, в которой большое внимание уделено безусловной нераскрываемости (в смысле Шеннона) секретной информации доказывающего [101], даже если проверяющий имеет неограниченные вычислительные мощности. Здесь же мы сосредоточимся на модели, в которой предполагаете^, что все затрагиваемые стороны должны иметь «разумные» вычислительные ресурсы.
