Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Интересная ситуация возникает, если рассматривать некоторый вариант протокола, в котором все раунды проводятся в параллель: Алиса принимает в качестве обязательств все до единого блобы, соответствующие к схемам таким, как на рис. 6.3, Боб передает ей строку с проверочными вопросами, и Алиса открывает блобы так, как того требует ответ на соответствующий вопрос. (В некоторых ситуациях этот вариант протокола может быть более эффективным.)
Предположим для простоты, что блобы — это битовые строки и что Алиса задается некоторым блобом, показывая его явно. Рассмотрим следующую стратегию для Боба: после получения от Алисы блобов, которые соответствуют всем к схемам со случайно переставленными строками и инвертированными столбцами таблиц истинности, он объединяет эти блобы вместе (конкатенируя их в одну строку) и использует полученный результат в качестве аргумента некоторой однонаправленной функции. Затем он использует первые к битов значения этой функции для определения к проверочных вопросов, которые будет ей задавать. Даже если проведение этого модифицированного протокола с Алисой и не помогает Бобу узнать что-либо о ее секрете, сама запись его может помочь ему убедить кого-нибудь еще в существовании этого секрета, поскольку Боб почти наверняка не сможет воспроизвести такую запись каким-то другим способом (даже если блобы являются моделируемыми). Это приводит к любопытному феномену: запись параллельной версии протокола может не содержать никакой информации о действительном
Доказательства с наименьшим раскрытием 109
секрете Алисы (в смысле шенноновской теории информации), даже несмотря на то, что такая запись может быть использована для убеждения кого-то еще в существовании этого секрета! . ;¦
Если важно, чтобы протокол проводился в параллель (возможно, из соображений большей эффективности), то полезно знать, что он остается протоколом с нулевым знанием, если определяющее его свойство 4’ еще более усилить. Мы скажем, что блобы являются хамелеонами, если в дополнение к свойствам 1,
2 и 3 они удовлетворяют свойству
4") Боб может смоделировать все, что должно быть обеспечено им в том процессе, с помощью которого Алиса принимает блобы в качестве обязательств. Более того, для каждого из этих блобов Боб может смоделировать как процесс, с помощью которого Алиса открывала бы их как 0, так и процесс, с помощью которого она открывала бы их как 1.
Иными словами, блобы-хамелеоны позволяют Бобу самому делать именно то, что свойство 2 предписывает делать Алисе, тем самым избавляя ее от этого. Преимущество блобов-хамелеонов заключается в том, что они предоставляют возможность Бобу моделировать напрямую весь свой диалог с Алисой. Это остается справедливым даже тогда, когда Боб произвольно отступает от предписанного ему поведения. Даже если Алиса и Боб имеют примерно одинаковые вычислительные ресурсы, это свойство может иногда достигаться в том случае, когда Боб обладает некоторой дополнительной информацией. Так, например, блобы (описанные в § 2), основанные на изоморфизме графов, являются хамелеонами, если и только если Боб знает изоморфизм графов G и Н, о которых идет речь. Соответственно первый из блобов, основанных на дискретном логарифме, является хамелеоном тогда и только тогда, когда Боб знает дискретный логарифм s. Это возможно, если вместо того чтобы выбирать случайным образом s, как это предлагалось ранее, он в интервале от 1 до р — 2 выбирает случайным образом число е, a s вычисляет как ае mod р. Однако такие двойственные блобы, основанные на дискретном логарифме, конечно, не являются хамелеонами, так как каждый из них определяет один бит однозначно.
Возникает естественный вопрос: кому лучше доверять—до-
110 Применения
Глава 6
называющему или проверяющему? «Мошенничество» приобретает разный смысл в зависимости от того, кто имеется при этом в виду, Алиса или Боб. Для Боба мошенничество означает, что он узнаёт что-то еще, кроме того факта, что Алиса имеет доступ к той информации, о владении которой она заявляет. Быть может, например, он и не получит полностью гамильтонову цепь, которую безуспешно пытается найти, но узнает достаточно для того, чтобы существенно сократить время ее поиска. С другой стороны, мошенничество для Алисы означает, что ей удается убедить Боба в том, что она обладает той информацией, которая будет подвергнута процедуре проверки, в то время как в действительности это не так.
Интересно также делать различие между удачным и дерзким типами успешного мошенничества [27]. Первый тип имеет отношение к отгадыванию Алисой, или Бобом, вопреки всем расчетам, той части информации, которая поможет ей, или ему, спокойно осуществить свой обман с уверенностью, что он будет успешным и не обнаружится. Ко второму типу обмана относится совершение Алисой, или Бобом, некоторых незаконных действий, которые в результате почти наверняка приведут к тому, что ее, или его, мошенничество будет обнаружено в определенный момент в будущем, но при этом, тем не менее, может с экспоненциально малой вероятностью привести ее, или его, к успеху. Наконец, мошенничество следует назвать ретроактивным (или автономным), если оно может иметь успех спустя какое-то время после завершения протокола при просмотре его записи. Такое мошенничество называется мошенничеством в реальном времени, если оно должно завершаться во время осуществления протокола.
