секрете Алисы (в смысле шенноновской теории информации), даже несмотря на то, что такая запись может быть использована для убеждения кого-то еще в существовании этого секрета? > i

Если важно, чтобы протокол проводился в параллель (возможно, из соображений большей эффективности), то полезно знать, что он остается протоколом с нулевым знанием, если определяющее его свойство 4 еще более усилить. Мы скажем, что блобы являются хамелеонами, если в дополнение к свойствам 1, 2 и 3 они удовлетворяют свойству

4") Боб может смоделировать все, что должно быть обеспечено им в том процессе, с помощью которого Алиса принимает блобы в качестве обязательств. Более того, для каждого из этих блобов Боб может смоделировать как процесс, с помощью которого Алиса открывала бы их как О, так и процесс, с помощью которого она открывала бы их как 1.

Иными словами, блобы-хамелеоны позволяют Бобу самому делать именно то, что свойство 2 предписывает делать Алисе, тем самым избавляя ее от этого. Преимущество блобов-хамелеонов заключается в том, что они предоставляют возможность Бобу моделировать напрямую весь свой диалог с Алисой. Это остается справедливым даже тогда, когда Боб произвольно отступает от предписанного ему поведения. Даже если Алиса и Боб имеют примерно одинаковые вычислительные ресурсы, это свойство может иногда достигаться в том случае, когда Боб обладает некоторой дополнительной информацией. Так, например, блобы (описанные в § 2), основанные на изоморфизме графов, являются хамелеонами, если и только если Боб знает изоморфизм графов G и Н, о которых идет речь. Соответственно первый из блобов, основанных на дискретном логарифме, является хамелеоном тогда и только тогда, когда Боб знает дискретный логарифм S. Это возможно, если вместо того чтобы выбирать случайным образом s, как это предлагалось ранее, он в интервале от 1 до р - 2 выбирает случайным образом число е, а s вычисляет как mod р. Однако такие двойственные блобы, основанные на дискретном логарифме, конечно, не являются хамелеонами, так как каждый из них определяет один бит однозначно.

Возникает естественный вопрос: кому лучше доверять - до-

казывающему или проверяющему? «Мошенничество» приобретает ргизный смысл в зависимости от того, кто имеется при этом в виду, Алиса или Боб. Для Боба мошенничество означает, что он узнаёт что-то еще, кроме того факта, что Алиса имеет доступ к той информации, о владении которой она заявляет. Быть может, например, он и не получит полностью гамильтонову цепь, которую безуспешно пытается найти, но узнает достаточно для того, чтобы существенно сократить время ее поиска. С другой стороны, мошенничество для Алисы означает, что ей удается убедить Боба в том, что она обладает той информацией, которая будет подвергнута процедуре проверки, в шо время как в действительности это не так.

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

Если используется блоб, который является безусловно надежным для Боба (в соответствии с протоколами, что приведены в [196, 78]), то Алиса может так никогда и не воспользоваться никакой частью своих знаний - Бобу может позволить ретроактивно смошенничать открытие какого-нибудь нового алгоритма, даже если этот новый алгоритм и не является достаточно быстрым для ответа за то реальное время, в течение которого проводится указанный выше протокол. Далее, если конкретное криптографическое предположение окажется не вполне обоснованным, для Боба все еще имеется (очень небольшая) вероятность удачного

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

В противоположность предыдушему, если используются блобы, дсоторые являются безусловно надежными для Алисы (в соответствии с протоколами, приведенными в [103, 79]), то убежденность Боба в том, что .Алиса не может смошенничать, зависит от его веры в соотвсгствуюшее криптографическое предположение. В соответствии с первой (из описанных в § 2) реализаций блобов, что основанына дискретном логарифме, Алиса, например, сможет «открыть» любой блоб либо как О, либо как 1, причем так, как ей это будет угодно, только если она будет в состоянии получить дискретный логарифм s до окончания первого раунда протокола, в котором Боб задает ей соответствую-шую сложную задачу. Получение этого логарифма в любое более позднее время было бы для нее бесполезно, так как в противном случае она не сможет подготовиться к ответу. Более того, если указанное криптографическое предположение является вполне обоснованным, то Алиса все еше имеет (очень небольшой) шанс попытаться отгадать его наудачу, но она должна набраться дерзости, чтобы предложить провести весь протокол в надежде, что ей и здесь повезет. С блобами, основанными на дискретном логарифме, у Боба нет вообще никакой возможности мошенничать, даже несмотря на везение и вычислительные ресурсы. Наконец, в рассматриваемой ситуации ретроактивное мошенничество является бессмысленным, как для Алисы, так и для Боба.

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