Научная литература
booksshare.net -> Добавить материал -> Физика -> Брассар Ж. -> "Современная криптология " -> 34

Современная криптология - Брассар Ж.

Брассар Ж. Современная криптология — М.: ПОЛИМЕД, 1999. — 178 c.
Скачать (прямая ссылка): sovremennayakritologiya1999.pdf
Предыдущая << 1 .. 28 29 30 31 32 33 < 34 > 35 36 37 38 39 40 .. 68 >> Следующая


Алиса выбирает случайно число х ? X, затем вычисляет значение у = f(x) и предъявляет его Бобу,

Боб пытается отгадать, является ли число х четным или нечетным, и объявляет свою догадку Алисе;

Алиса сообщает Бобу, оказался он прав или нет, и доказывает ему это, раскрывая х;

Боб посредством проверки f{x) = у либо подтверждает, либо опровергает честность Алисы.

Суть представленного протокола заключается в том, что Алиса связывает себя (в качестве обязательства) числом х, ввиду того что она сообщает Бобу значение y=f(x), однако Боб, зная у, не может вычислить х самостоятельно, потому что функция / является однонаправленной. (В § 2 мы предпримем более детальное обсуждение общего понятия подобного битового обяза-
Бросание жребия 89

телъства.) Интуитивно ясно, что этот протокол является конструктивным, хотя если функция / была выбрана недостаточно тщательно (даже если она и в самом деле однонаправленная), то он все равно оставляет дверь открытой для мошенничества как со стороны Алисы, так и со стороны Боба.

Если функция / не является взаимнооднозначной, то возможно, что Алиса, знает такие числа жиж, для которых f(x) = f(x) и при этом сумма х + х которых нечетна (что заранее не включалось в определение однонаправленности). В таком случае она может объявить у = /(ж), фактически не связывая себя обязательством ни посредством х, ни посредством х. Следовательно, если бы это было так, то Алиса могла бы смошенничать. С другой стороны, может быть так, что функция / взаимнооднозначна и что вычисление х из f(x) практически трудноосуществимо, но его то как раз делать заведомо и не обязательно, поскольку оказывается, что четность числа х может быть легко определена из вида самого значения f(x). Но даже, если бы четность х будет трудно определить в точности для данного значения f(x), может статься, что ее можно угадать с вероятностью успеха более, чем 50%. В этой ситуации мог бы мошенничать Боб.

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

Алиса выбирает случайным образом какое-нибудь число Блюма п и некоторое х ? Жп, затем вычисляет у = х2 mod п и г = у2 mod тг, после чего сообщает числа лиг Бобу;

Боб объявляет Алисе свое предположение о том, является ли число у чётным или нечетным;

Алиса раскрывает Бобу числа а; и у, а также позволяет ему убедиться в том, что п является числом Блюма;

Боб проверяет, что и в самом деле у = х2 mod тг, а z — y2 mod п.

Иными словами, Алиса передает Бобу квадратичный вычет z по модулю целого числа Блюма, а Боб проверяет, является ли его примитивный квадратный корень четным или нечетным. В
90 Применения

Глава 6

этом случае Боб, как мы уже видели в § 4.5, чтобы высказать свое предположение, не может найти ничего лучшего, чем бросить жребий. С другой стороны, критично, что п является целым числом Блюма, так как в противном случае могло бы быть так, что z имеет два квадратных корня различной четности, оба из которых являются квадратичными вычетами. Вот почему Алиса должна позволить Бобу «убедиться в том, что п является целым числом Блюма». Для этого Алиса может сообщить Бобу разложение п на множители (теперь для Боба будет уже слишком поздно использовать эту информацию, с тем чтобы повлиять на результат своего выбора). Если же Алиса хочет применять свое целое число Блюма п еще и для других целей или использовать его в нескольких жеребьевках, то она, для того чтобы убедить Боба в своей добропорядочности, может воспользоваться интерактивным протоколом минимального раскрытия [206]. Смотрите также § 3.

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

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

§ 2. Схемы битовых обязательств

(написало вместе с Клодом Крепеу и Дэвидом Чаумом)

Понятие битового обязательства является сильным И общим примитивом для разработки секретных криптографических протоколов. Цель битового обязательства заключается в том, чтобы позволить Алисе взять на себя в качестве обязательства значение некоторого бита информации таким способом, который не позволяет Бобу узнать это значение без ее помощи, но который также не позволяет и самой Алисе его изменить. Если возможна нераскрываемая схема битовых обязательств, то бросание жребия (так, как оно описано в § 1) становится тривиальным в реализации: Алиса берет на себя в качестве обязательства значение некоторого случайно выбранного бита, Боб угадывает это значение и аннонсирует свою догадку, а Алиса показывает ему, догадался ли он на самом деле или нет. Более тщательно проработанное применение схемы битовых обязательств описывается в следующем параграфе.
Предыдущая << 1 .. 28 29 30 31 32 33 < 34 > 35 36 37 38 39 40 .. 68 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed