Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Что касается свойств, определяющих блобы, то в приведен-
94 Применения
Глава 6
ном примере свойство (а) выполнено потому, что Алиса может задаться битом 0 (соответственно 1), случайным образом переставив вершины G (соответственно Н) и предъявив получившийся граф-блоб Бобу. Для того чтобы раскрыть блоб, Алисе достаточно указать Бобу этот известный ей изоморфизм для любого из двух графов, G или Н¦ Свойство (Ь) выполняется, если и только если Алиса не может найти изоморфизма между G и Я. Точнее, для того чтобы Алиса могла нарушить свойство (Ь), она должна получить такую информацию, которая позволит ей легко обнаружить подобный изоморфизм. Свойство (с) безусловно справедливо, потому что блобы, используемые Алисой в качестве обязательства 0, в теоретико-информационном смысле неотличимы от тех, что используются как обязательство 1 — ведь и те, и другие являются случайными изоморфными копиями G (а, следовательно, и Я). Наконец, свойство (d) удовлетворяется, потому что Алиса переставляет вершины G случайным образом, то есть таким способом, при котором перестановка не коррели-руется ничем вообще.
Таким образом, приведенный выше пример иллюстрирует именно тот случай, в котором не блоб сам по себе (некий граф, который изоморфен и G, и Я) определяет некоторый бит информации, а, скорее, знание Алисы об этом блобе (фактический изоморфизм, известный Алисе, между этим графом и либо графом G, либо графом Я).
Более практичный, хотя в техническом отношении и более сложный пример такого же типа схемы битовых обязательств основан на предположении о трудности решения задачи дискретного логарифмирования (см. § 4.1) [112, 62]. Пусть р — большое простое число и пусть а является примитивным (первообразным) корнем по модулю р (порождающим Ж* — мультипликативную группу обратимых элементов кольца классов вычетов по модулю р). Напомним, что для любого заданного целого числа у можно легко вычислить ay mod р, но до сих пор не известно никакого эффективного алгоритма обращения этой процедуры./ Более того, предположим, что вычисление у из, а, р и ау mod р остается практически невыполнимымг даже если известно разложение числа р— 1.
Сначала Алиса и Боб договариваются о подходящем простом числе р, для которого им обоим известно разложение числа р— 1.
Схемы битовых обязательств 95
Они также договариваются об а, генераторе Z*. Благодаря своему знанию множителей р — 1, они оба могут с определенностью убедиться, что р ив самом деле простое число, а а является генератором Z* [236]. Указанные параметры р и а могут быть сделаны общедоступными в том смысле, что к ним можно предоставить доступ всем, кто захочет принять участие в протоколах битовых обязательств. Вначале Боб выбирает, помимо всего прочего, случайное число s ? Z* такое, что s ф 1, и передает его Алисе. Согласно нашему предположению, Алиса не может вычислить е, 0 $5 е <С р — 2, для которого s = a6 (mod р).
Затем, для того чтобы принять в качестве обязательства значение некоторого бита Ь, Алиса выбирает случайным образом число у, лежащее в интервале от 0 до р — 2, и вычисляет х = sbay mod р. После этого она передает х, которое и является блобом, Бобу, но сохраняет в секрете у в качестве своего удостоверения этого блоба, позволяющего ей открывать х как бит Ь. Ясно, что как в качестве обязательства 0, так и в качестве обязательства 1, Алисой может быть использован любой элемент Z*, который зависит только от ее знаний о нем. Более того, элементы Z*, получающиеся с помощью этого процесса, имеют равномерное распределение вероятностей, независящее от того бита, который Алиса пожелает взять в качестве обязательства. Следовательно, свойство (с) здесь также безусловно справедливо — блобы, принятые в качестве обязательств Алисой, не содержат никакой информации о том способе, которым она могла бы их раскрыть. Свойство (Ь) удовлетворяется в вычислительном смысле, потому что Алиса могла бы легко получить е (что, как мы предположили, является для нее практически неосуществимым) из знания г/о и 2/1 таких, что ayQ ~ s ¦ а\ (mod р), поскольку тогда е = г/i — j/г rn°d [р — 1). Наконец, свойство (d) выполняется, потому что Алиса выбирает у случайно.
Предположение о трудности решения задачи дискретного логарифмирования может также использоваться для реализации схемы битовых обязательств дуального типа [78]. Снова, пусть р — большое простое число, и пусть а является генератором Z*. Пусть и — наименьшее целое, такое, что 2“ не делит р — 1. Для любого заданного s € Z* обозначим через hard(s) u-тый младший значащий бит единственного Целого числа е, такого, что 0 ^ е ^ р — 2 и в = ае mod р. В предположении о сложности
96 Применения
Глава 6
задачи дискретного логарифмирования практически ничего невозможно узнать о hard(s) (при заданных лишь р, а и случайно выбранном s), потому что доказано, что решение этой задачи является столь же трудным, сколь и само дискретное логарифмирование (в сильном вероятностном смысле) [285] (хотя и — 1 младших значащих битов е могут быть легко вычислены для данного s).
