Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Битовое обязательство реализуется посредством некоторого основного понятия, которое мы назовем «блобом». Каждый блоб используется как обязательство либо 0, либо 1. Из соображений общности мы не накладываем никаких ограничений на природу блобов. Они могут быть сделаны даже из «улыбки чеширского кота» (или из поляризованного фотона!), если это окажется полезным. Под словами: «Алиса берет (принимает на себя) в качестве обязательства некоторый блоб», или, короче: «Алиса задается некоторым блобом», мы понимаем, что Алиса хранит конкретное значение, соответствующее данному блобу «в уме» и во всех своих последующих действиях придерживается именно этого значения. Если блоб сам по себе может быть представлен в виде битовой строки, как оказывается в большинстве практических случаев, то демонстрацией принятия блоба в качестве обязательства может быть просто показ его в явном виде.
Абстрактными свойствами, которые определяют блобы, являются следующие:
(а) Алиса может принять блобы в качестве обязательств: задаваясь некоторым блобом, она в сущности принимает в качестве 'обязательства некоторый бит.
92 Применения
Глава 6
(b) Алиса может раскрыть любой блоб, который она приняла в качестве обязательства. При этом она может убедить Боба в том, что действительно задавалась именно указанным ею значением соответствующего бита информации, когда принимала в качестве обязательства данный блоб. Таким образом, никакой из блобов не может быть «раскрыт» ею и как 0, и как 1.
(c) Боб не в состоянии узнать ничего о том, каким образом Алиса может раскрыть какой бы то ни было нераскрытый блоб, который она приняла как обязательство. Это остается справедливым даже после того, как другие блобы уже были раскрыты Алисой.
(d) Блобы не содержат никакой побочной информации: блобы сами по себе, так же как и тот процесс, посредством которого Алиса принимает их в качестве обязательств и раскрывает, не коррелируется никаким другим секретом, который она может захотеть утаить от Боба.
Рассмотрим следующую иллюстрацию реализации блоба. Когда Алиса хочет принять в качестве обязательства некоторый бит (свойство (а)), она пишет его значение на полу и до того, как Боб сможет его увидеть, заклеивает его непрозрачной липкой лентой. Тогда, с одной стороны, Боб не может сказать, какой бит скрыт под лентой (свойство (с)), а с другой — Алиса после этого в присутствии Боба уже не может изменить значение заклеенного бита. Для того чтобы «раскрыть блоб» (свойство (Ь)), Алиса позволяет Бобу отклеить ленту и взглянуть на этот бит. Свойство (d) удовлетворяется, если ни способ, с помощью которого значение бита было записано на полу, ни сама лента, ни ее местоположение не коррелируются никаким секретом, который Алиса могла бы захотеть скрыть от Боба.
Если блобы используются в рамках общепринятого криптографического протокола, в процессе которого происходит обмен электронными сообщениями, то сами они также должны быть представлены в цифровом виде. В этом случае, казалось бы, налицо явное противоречие между свойствами, которым должны удовлетворять блобы. Из свойства (Ь) следует, что блобы, которые Алиса может открыть как 0, должны отличаться от тех,
Схемы битовых обязательств 93
которые она может открыть как 1. Но тогда что же воспрепятствует Бобу обнаружить это различие и нарушить, таким образом, свойство (с)?
Суть одного из возможных ответов на такой вопрос состоит в том, что значение принятого бита должно определяться не самим по себе блобом, а скорее знанием Алисы о нем. Если эту идею реализовать аккуратно, то для Боба становится невозможным узнать что бы то ни было о том, каким образом Алиса может раскрыть любой еще нераскрытый ею блоб, который она приняла в качестве обязательства. Причем можно добиться, что это будет справедливо в самом сильном теоретико-информационном смысле. Тем не менее дополнительные знания могут в принципе позволить Алисе нарушить свойство (Ь).
С другой стороны, если мы настаиваем на том, чтобы свойство (Ь) выполнялось безусловно, требуется принять двойственное решение, заключающееся в том, что блобы, используемые Алисой как обязательство 0, должны быть отличимы от тех, которые она использует в качестве обязательства 1. В этом случае она неизбежно задается неким особым битом всякий раз, когда принимает в качестве обязательства некоторый блоб, и, как следствие этого, Боб может в принципе нарушить свойство (с). Несмотря на то, что оба подхода предоставляют возможность одной из сторон смошенничать, это может быть сделано вычислительно неосуществимым при соответствующих криптографических предположениях.
В качестве элементарного (хотя, быть может, и не очень надежного) примера рассмотрим два изоморфных графа G и Н, о которых Алиса и Боб условились заранее. Предположим, что Алиса убеждена в том, что они изоморфны, хотя в действительности и не знает никакого изоморфизма между ними. Более того, предположим, что она неспособна в вычислительном смысле найти такой изоморфизм за приемлемое время. (Давайте отложим до § 3 вопрос о том, каким образом Алиса может убедиться в том, что данные графы являются изоморфными, не узнав при этом самого изоморфизма.) В этих предположениях Алиса договаривается с Бобом, что любой граф, для которого она сможет указать изоморфизм с G (соответственно с Н) является принятием в качестве обязательства бита 0 (соответственно 1).
