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

В этом параграфе мы опишем общий и эффективный протокол для проведения доказательств с наименьшим раскрытием. Этот протокол позволяет Алисе убедить Боба после любого его разумного сомнения в том, что она действительно обладает некой информацией, которая с успехом пройдет проверяющую процедуру, но способ, которым она это делает, никоим образом не помогает ему определить саму эту информацию. Например, если такой информацией Алисы является доказательство какой-нибудь теоремы, то Боб будет в полной уверенности, что Алиса действительно знает, как ее доказывать, и, следовательно, что теорема верна. Однако Бобу при этом не предоставится никакого намека на то, как такое доказательство (за исключением разве что верхней границы на его длину) можно было бы осуществить ему самому. Следовательно, несмотря на то, что оригинальная информация Алисы является проверяемой, та убежденность в ее справедливости, которую получает Боб, фактически ничего ему не дает. В частности, проведение протокола с Алисой не обяза но (а во многих случаях и не будет) предоставлять возможности Бобу впоследствии убедить в этом таким же образом кого-нибудь еще.

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

ею в секрете утверждении. Поскольку Алиса не может раньше времени предугадать, какой из вопросов задаст Боб, то каждый рауйд протокола увеличивает его уверенность в справедливости ее секрета. В действительности она может надеяться обдурить его за к успешных раундов с экспоненциально уменьшающейся вероятностью 2~*. Мы будем называть такую технику приемом разрезания-и-выбора, поскольку каждый ее раунд подобен классическому «протоколу», с помощью которого двое детей делят кусок торта - один из них режет, а другой выбирает ту часть, которая ему больше нравится. Необычайная полезность приема «разрезания-и-выбора» состоит в том, что она обеспечивает экспоненциально возрастающую уверенность ценой лишь линейного увеличения числа раундов.

Самое раннее использование техники «разрезания-и-выбора», которое нам известно в связи с криптографическими интерактивными протоколами, было предложено Майклом Рабином в 1977 году [296]. Понятие интерактивного протокола было впоследствии формализовано, а Шафи Гольдвассер, Сильвио Микэли и Чарльзом Раковом в [199] было введено понятие нулевого знания . (Понятие нулевого знания сходно с понятием минимального ргкскрытия, за исключением того, что оно требует, чтобы Боб не мог получить из протокола вообще ничего, кроме знания о том, что Алиса обладает той информацией, о которой она заявляет.) Ласло Бабаи формализовал также понятие, сходное с понятием интерактивных протоколов [11]. Модели, представленные в [199, 11], предполагают, что доказывающий обладает неограниченными вычислительными ресурсами. Дэвидом Чаумом была предложена несколько иная модель, в которой большое внимание уделено безусловной нераскрываемости (в смысле Шеннона) секретной информации доказывающего [101], даже если проверя-юпщй имеет неограниченные вычислительные мощности. Здесь же мы сосредоточимся на модели, в которой предполагаете!, что все затрагиваемые стороны должны иметь «разумные» вычислительные ресурсы.

Рассмотрим довольно простой, но элегантный пример предложенного Одедом Голдрейчем, Сильвио Микэли и Эви Вигдерсо-ном [196] протокола доказательства с минимальным раскрытием, который позволяет Алисе убедить Боба в том, что она знает некоторый изоморфизм между двумя заданными графами G и Я,

таким образом, что это никаж не помогает Бобу разгадать этот изоморфизм. Данный пример иллюстрирует применение принципа «разрезания-и-выбора» (и раскрывает ссылку, которая была сделана в конце § 2 в том абзаце, где приводится описание примера схемы битового обязательства, основанной на изоморфизме графов). В произвольном раунде этого протокола Алиса случайно переставляет вершины G, чтобы получить некоторый граф К, изоморфный как графу О, так и графу Я, и передает К Бобу. Очевидно, что если Алиса правдива, то она должна знать также и изоморфизм между Н и К (посредством композиции сделанной перестановки с перестановкой, определяющей изоморфизм между G и Я, о знании которого она заявила).

После этого Боб выбирает G или Я и предлагает Алисе предоставить ему изоморфизм между выбранным им графом и К. Ясно, что Алиса в состоянии решить эту трудную задачу, только если она не врет. Однако Алиса, вне зависимости от того, каким способом она получает К (даже полагая, что она попытается мошенничать), не сможет быть готова ответить на оба возможных вопроса, если она в действительности не знает изоморфизма между О и Н. Следовательно, поскольку Алиса не может! предсказывать, какой из вопросов будет поставлен Бобом, любая ее попытка смошенничать будет выявлена им с вероятностью равной по крайней мере одной второй. Вероятность не выявленного обмана может быть, таким образом, сделана сколь угодно малой при помощи повторения этого процесса достаточно большое число раз. Несколько труднее, однако, увидеть, что этот протокол не в состоянии помочь Бобу определить изоморфизм между графами О и Н. Для выяснения дальнейших деталей обращайтесь к [196].

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