Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
Вообразите нападение террористов на Нью-Йорк, какие бы ограничения не были бы сметены полицией, чтобы остановить последствия? Трудно представить себе, что эти условные схемы шифрования, как говорят их защитники, будут использ о- ваться без принуждения извне. Следующим очевидным шагом будет запрет на использование всех других сп о- собов шифрования. Это, вероятно, единственный способ добиться коммерческого успеха этой системы, и это, определенно, единственный способ заставить технически грамотных преступников и террористов использовать ее. Пока не ясно, насколько трудно будет объявить не-условную криптографию вне закона, или как это повлияет на криптографию как на академическую дисциплину . Как я могу исследовать программно ориентированные алгоритмы криптографии, не имея доступа к программному обеспечению устройств не-условного шифрования, нужна ли мне будет специальная лицензия? И другие законные вопросы. Как условно врученные ключи повлияют на ответственность пользователей, должна ли становиться известной зашифрованная информация ? Если правительство США пытается защитить органы условного вручения, не будет ли это косвенным свидетельством того, что если секрет скомпрометирован либо пользователем, либо органами условного вручения, то виновником будет признан пользов атель? Что если база данных главной службы условного вручения ключей, все равно государственной или комме р- ческой, будет украдена? Что, если правительство США попытается ненадолго скрыть этот факт ? Ясно, что все эти вопросы повлияют на желание пользователей пользоваться условным вручением ключей . Если использова- ние не будет добровольным, то пара скандалов вызовет рост политического давления с целью либо сделать и с- пользование подобных систем добровольным, либо ввести новые сложные правила в этой отрасли . Еще более опасным будет скандал, когда выяснится, что годами под наблюдением находился политический оппонент текущей администрации или некий громкоголосый критик спецслужб и полицейских ведомств . Это сильно настроит общественное мнение против условного шифрования . Если ключи подписей будут шифроваться тем же способом, что и ключи шифрования, возникнут дополн и- тельные моменты. Допустимо ли для властей использовать ключи подписей для проведения операции против подозреваемого преступника? Будет ли признана судом подлинность подписей, основанных на ключах с усло в- ным вручением? Чем в действительности будут владеть пользователи, если власти действительно используют их ключи пользователей для подписи какого-то невыгодного контракта, для поддержки определенных отраслей промышленности, или просто, чтобы украсть деньги ? Глобальное распространение криптографии рождает дополнительные вопросы. Будут ли схемы условного вручения ключей совместимы в различных странах ? Захотят ли транснациональные корпорации смириться с существованием в каждой стране своих условно врученных ключей, совместимых с различным местным зак о- нодательством? Без обеспечения совместимости исчезает одно из пропагандируемых преимуществ схемы с у с- ловным вручением ключей (международное использование мощных средств криптографии) . Что если ряд стран не примет на веру надежность организаций, связанных с условным вручением ключей? Как будут пользователи вести свои дела в этих странах ? Будут ли признаны судами их электронные контракты, или тот факт, что ключи их подписей условно хранятся в США, позволит им утверждать где-нибудь в Швейц а- рии, что этот электронный контракт мог подписать кто-то другой ? Или для людей, которые ведут дела в подо б- ных странах, будут специальные исключения? А что делать с промышленным шпионажем? Где гарантии, что страны, занимающиеся сейчас промышле н- ным шпионажем для своих важнейших или государственных предприятия, не воспользуются для этого сист е- мами с условным вручением ключей? В самом деле, так как ни одна страна не собирается позволять другим странам следить за своими разведывательными операциями, распространение условного шифрования возможно приведет к увеличению подслушивания. Даже если страны, в которых соблюдаются гражданские права, будут использовать условность такого ши ф- рования только для законного преследования преступников и террористов, где-нибудь этим обязательно во с- пользуются для выслеживания диссидентов, шантажа политических оппонентов, и т.п. Цифровые линии связи предоставляют возможность гораздо более тщательно, чем это было возможно в аналоговом мире, контролир о- вать действия граждан, их мнения, Digital communications offer the opportunity to do a much more thorough lob of monitoring citizens' actions, opinions, доходы и объединения. Не ясно, не будет ли через 20 лет продажа системы с условным вручением ключей Турции или Китаю пох о- дить на продажу электрических дубинок Южной Африке в 1970 году или на строительство химического завода в Ираке в 1980 году. Даже хуже, легкое и незаметное подслушивание линий связи может искусить многие пр а- вительства, которые раньше, возможно, этим и не занимались, следить за корреспонденцией своих граждан . И нет гарантии, что либеральные демократии устоят перед подобным искушением . Глава 5 Развитые протоколы 5.1 Доказательства с нулевым знанием А вот другая история: Алиса: "Я знаю пароль компьютера Федеральной Резервной Системы, компоненты секретного соуса МакДональдс и оде р- жание 4-го тома Дональда Кнута". Боб: "Нет, ты не знаешь". Алиса: "Нет, я знаю". Боб: "Не знаешь". Алиса: "Нет, знаю". Боб: "Докажи". Алиса: "Хорошо, я скажу тебе". Она шепчет Бобу на ухо. Боб: "Это интересно. Теперь я тоже это знаю и собираюсь рассказать это все Вашингтон Пост". Алиса: "Оооой". К несчастью, обычно Алиса может доказать что-нибудь Бобу, только рассказав ему все. Но тогда он тоже получит все сведения. Затем Боб может выложить полученные сведения кому угодно, и Алиса ничего не сможет с этим поделать. (В литературе для описания этих протоколов часто используются различные персонажи . Пегги обычно доказывает, а Виктор проверяет. Именно эти имена появляются в используемых примерах вместо Ал и- сы и Боба.) Используя однонаправленные функции, Пегги сможет провести доказательство с нулевым знанием [626]. Этот протокол доказывает Виктору, что у Пегги действительно есть информация, но не дает Виктору не мале й- шей возможности узнать, что это за информация . Эти доказательства принимают форму интерактивного протокола. Виктор задает Пегги ряд вопросов. Если Пегги знает секрет, то она ответит на все вопросы правильно. Если секрет ей неизвестен, у нее есть некоторая вероятность - 50 процентов в следующих примерах - ответить правильно . После примерно 10 вопросов Виктор убедится, что Пегги знает секрет. Но ни один из вопросов или ответов не даст Виктору ни малейших сведений об информации Пегги, но докажет знание Пегги этой информации . Базовый протокол с нулевым знанием Жан-Жак Кискатер (Jean-Jacques Quisquater) и Луи Гилу (Louis Guillou) поясняют нулевое знание историей о пещере [1281]. У пещеры, показанной на 4-й, есть секрет. Тот, кто знает волшебные слова может открыть п о- тайную дверь между C и D. Для всех остальных оба прохода ведут в тупик . +, * А Рис. 5-1. Пещера нулевого знания Пегги знает секрет пещеры. Она хочет доказать свое знание Виктору, но не хочет раскрывать волшебных слов. Вот как она убеждает его: (1) Виктор находится в точке А. (2) Пегги проходит весь путь по пещере, либо до точки C, либо до точки D. (3) После того, как Пегги исчезнет в пещере, Виктор переходит в точку В. (4) Виктор кричит Пегги, спрашивая ее либо о: (a) или выйти из левого прохода (b) выйти из правого прохода. (5) Пегги исполняет его просьбу, при необходимости используя волшебные слова, чтобы отпереть дверь. (6) Пегги и Виктор повторяют этапы (1) - (5) n раз. Предположим, что у Виктора есть видеокамера, и он записывает все, что видит . Он записывает, как Пегги исчезает в пещере, записывает, как он сам кричит, указывая, где Пегги должна появиться, записывает как Пегги появляется. Он записывает все n тестов. Если он покажет эту видеозапись Кэрол, поверит ли она, что Пегги зн а- ет волшебные слова, отпирающие дверь? Нет. А что если Пегги и Виктор заранее договорились, что Виктор будет кричать, а Пегги будет делать вид, что она прошла весь путь. Тогда она будет каждый раз выходить из указанного Виктором места, не зная волшебных слов. Или они могли сделать по другому. Пегги входит в один из проходов и Виктор случайным образом выкрикивает свои просьбы . Если Виктор угадывает правильно, хо- рошо, если нет - они вырежут эту попытку из видеозаписи . В любом случае Виктор может получить видеоза- пись, показывающую в точности ту последовательность, которая получилась бы, если бы Пегги знала волше б- ные слова Этот опыт показывает две вещи. Во первых, Виктор не может убедить третью сторону в правильности док а- зательства. И во вторых, данный протокол является протоколом с нулевым знанием . Если Пегги не знает вол- шебных слов, то очевидно, что Виктор не узнает ничего из просмотра видеозаписи . Но так как нет способа от- личить реальную видеозапись от подделанной, то Виктор не может ничего узнать из реального доказательства - это и есть нулевое знание. Методика, используемая в этом протоколе, называется разрезать и выбрать из-за того, что она похож на классический протокол честного деления чего-либо : (1) Алиса делит некую вещь пополам. (2) Боб выбирает одну из половин себе. (3) Алиса забирает оставшуюся половину. В интересах Алисы честно разделить на этапе (1), потому что Боб выберет на этапе (2) ту половину, которая ему больше нравится. Майкл Рабин (Michael Rabin) первым использовал в криптографии технику "разрезать и выбрать" [1282]. Понятия интерактивного протокола и нулевого знания были формализованы позже [626, 627]. Протокол "разрезать и выбрать" работает, потому что Пегги не может несколько раз подряд угадывать, отк у- да Виктор попросит ее выйти. Если Пегги не знает секрета, он может выйти только из того прохода, в который она зашла. В каждом раундепротокола ее вероятность (иногда называемая аккредитацией) угадать, с какой стороны Виктор попросит ее выйти, составляет 50 процентов , поэтому ее вероятность обмануть Виктора также равна 50 процентам. Вероятность обмануть его в двух раундах составит 25 процентов , а во всех n раундах - один шанс из 2 n . После 16 раундов у Пегги 1 шанс из 65536 обмануть Виктора. Виктор может уверенно предпо- ложить, что если все 16 доказательств Пегги правильны, то она действительно знает тайные слова, открыва ю- щие дверь между точками C и D. (Аналогия с пещерой несовершенна. Пегги может просто входить с одной сто- роны и выходить с другой, протокол "разрезать и выбрать" не нужен . Однако, он необходим с для нулевого зна- ния с математической точки зрения.) Предположим, что Пегги известна некоторая информация, которая является решением трудной проблемы . Базовый протокол нулевого знания состоит из нескольких раундов . (1) Пегги использует свою информацию и случайное число для преобразования одной трудной проблемы в другую, изоморфную оригинальной проблеме . Затем она использует свою информацию и случайное число для решения новой трудной проблемы. (2) Пегги вручает решение новой проблемы, используя схему вручения бита. (3) Пегги раскрывает Виктору новый экземпляр проблемы. Виктор не может использовать эту новую пробл е- му для получения информации о первоначальной проблеме или ее решении. (4) Виктор просит Пегги либо (a) доказать ему, что новая и старая проблема изоморфны (т.е., два различных решения для двух св я- занных проблем), либо (b) открыть решение, полученное на этапе (2) и доказать, что это решение новой проблемы. (5) Пегги исполняет его просьбу. (6) Пегги и Виктор повторяют этапы (1) - (5) n раз. Помните видеокамеру в протоколе для пещеры? Здесь вы можете сделать то же самое . Виктор может запи- сать обмен между ним и Пегги. Он не сможет использовать эту запись для убеждения Кэрол, но он всегда м о- жет сговориться с Пегги с целью создать имитатор, который подделывает информацию Пегги . Этот аргумент может быть использован, чтобы доказать, что используется доказательство с нулевым знанием . Математическая основа доказательства этого типа сложна. Проблемы и случайное преобразование должны выбираться осторожно, чтобы Виктор не получил никакой информации о решении оригинальной проблемы, даже после многих повторений протокола . Не все трудные проблемы можно использовать для доказательств с нулевым знанием, но большинство из них . Изоморфизм графа Объяснение этого понятия, пришедшего из теории графов [619, 622], может занять некоторое время. Граф представляет собой сеть линий ,соединяющих различные точки. Если два графа идентичны во всем, кроме имен точек, они называются изоморфными. Для очень больших графов доказательство их изоморфности может п о- требовать веков компьютерного времени , это одна из так называемых NP-полных проблем, рассматриваемых в разделе 11.1. Предположим, что Пегги знает об изоморфности двух графов , G 1 и G 2 . Следующий протокол докажет Вик- тору знание Пегги: (1) Пегги случайным образом тасует G 1 , получая другой граф, Н, который изоморфен G 1 . Так как Пегги знает об изоморфизме Н и G 1 , то ей также известен изоморфизм между Н и G 2 . Для любого другого поиск изо- морфизма между Н и G 1 или Н и G 2 является такой же трудной задачей, как и поиск изоморфизма между G 1 и G 2 (2) Пегги посылает Н Виктору. (3) Виктор просит Пегги либо (a) доказать, что Н и G 1 изоморфны, либо (b) доказать, что Н и G 2 изоморфны. (4) Пегги исполняет его просьбу. Она либо: (a) доказывает, что Н и G 1 изоморфны, не доказывая, что Н и G 2 изоморфны, либо (b) доказывает, что Н и G 2 изоморфны, не доказывая, что Н и G 1 изоморфны. (5) Пегги и Виктор повторяют этапы (1) - (4) n раз. Если Пегги не знает об изоморфизме между G 1 и G 2 , она не сможет создать граф Н, изоморфный обоим гра- фам. Она может создать либо граф, который изоморфен G 1 , либо граф, который изоморфен G 2 . Как и в преды- дущем примере у нее только 50 шансов из 100 угадать, какое доказательство потребует от нее Виктор на этапе (3). Этот протокол не дает Виктору никакой полезной информации, помогающей ему из ответов Пегги устан о- вить изоморфизм между G 1 и G 2 . Так как Пегги для каждого нового раунда протокола генерирует новый граф Н, Виктор не сможет получить информацию независимо от того, из скольких раундов будет состоять их протокол . Он не сможет из ответов Пегги установить изоморфизм между G 1 и G 2 В каждом раунде Виктор получает новое случайное преобразование Н, вместе с изоморфизмом между Н и G 1 или G 2 . Виктор может также создать что-то подобное самостоятельно. Так как Виктор может создать имитацию протокола, это действительно доказательство с нулевым знанием . Гамильтоновы циклы Вариант этого примера был впервые представлен Мануэлем Блюмом ( Manuel Blum) [196]. Пегги знает кружной, продолжительный путь вдоль линий графа, который проходит через каждую точку только один раз . Этот путь называется гамильтоновым циклом. Поиск гамильтонова цикла является другой тяжелой задачей . У Пегги есть эта информация - она, возможно, получила ее создав граф с конкретным гамильтоновым циклом - и она хочет доказать Виктору, что эта информация ей известна . Пегги знает гамильтонов цикл графа, G. Виктору известен G, но не его гамильтонов цикл. Пегги хочет дока- зать Виктору, что она знает гамильтонов цикл, не раскрывая самого цикла . Вот как она должна действовать: (1) Пегги случайным образом преобразовывает G. Она передвигает точки и изменяет их метки, создавая н о- вый граф, H. Поскольку G и H топологически изоморфны (т.е., это один и тот же граф), если ей известен гамильтонов цикл G, то она легко может найти гамильтонов цикл H. Если она не сама создает H, опреде- ление изоморфизма между двумя графами будет являться другой сложной проблемой, решение которой также потребует веков компьютерного времени . Затем она шифрует H, получая H'. (Должно использовать- ся вероятностное шифрование каждой строчки H, то есть, шифрованный 0 или шифрованная 1 для каждой линии H.) (2) Пегги передает Виктору копию H. (3) Виктор просит Пегги либо: (a) доказать ему, что Н' - это зашифрованная изоморфная копия G, либо (b) показать ему гамильтонов цикл для Н. (4) Пегги исполняет его просьбу. Она либо: (a) доказывает, что Н' - это зашифрованная изоморфная копия G, раскрывая преобразования и расшиф- ровывая все, не показывая гамильтонов цикл для G или Н, либо (b) показывает гамильтонов цикл для Н, расшифровывая только те строки, которые образуют гамил ь- тонов цикл, не доказывая, что Н и G топологически изоморфны. (5) Пегги и Виктор повторяют этапы (1) - (4) n раз. Если Пегги не обманывает, она сможет предъявить Виктору одно из доказательств на этапе (3) . Однако, если гамильтонов цикл для G ей неизвестен, она не сможет создать зашифрованный граф H', который удовлетворяет обоим доказательствам. Лучшее, что она может сделать - это создать или граф, изоморфный G, или граф с та- ким же числом точек и линий и правильным гамильтоновым циклом . Хотя ее шансы угадать, какое доказатель- ство потребует Виктор на этапе (3), составляют 50 процентов, Виктор может повторить протокол достаточное число раз, убеждаясь, что Пегги знает гамильтонов цикл для G. Параллельные доказательства с нулевым знанием В базовом протоколе с нулевым знанием используется n обменов информацией между Пегги и Виктором . Почему бы не выполнить их параллельно : (1) Пегги использует свою информацию и n случайных чисел для преобразования трудной проблемы в n раз- личных изоморфных проблем. Затем она с помощью своей информации и случайных чисел решает n но- вых трудных проблем. (2) Пегги вручает решение n новых трудных проблем. (3) Пегги раскрывает Виктору эти n новых трудных проблем. Виктор не может воспользоваться этими нов ы- ми проблемами для получения информации об оригинальных проблемах или их решении. (4) Для каждой новой трудной проблемы Виктор просит Пегги либо (a) доказать ему, что старая и новая проблемы изоморфны, либо (b) раскрыть решение, врученное на этапе (2), и доказать, что оно является решением данной новой проблемы. (5) Пегги исполняет его просьбу для каждой новой проблемы. К несчастью, все не так просто. Этот протокол, в отличие от предыдущего, не обладает такими же свойств а- ми нулевого знания. На этапе (4) Виктор может потребовать, чтобы доказательство было представлено в виде значения однонаправленной хэш-функции всех значений, врученных на первом этапе, делая невозможным им и- тацию записи протокола. Это тоже нулевое знание, но другого рода . На практике оно представляется безопас- ным, но никто не знает, как это доказать . Мы действительно знаем только то, что при определенных условиях определенные протоколы для определенных проблем могут быть выполнены параллельно без потери свойства нулевого знания [247, 106, 546, 616]. Неинтерактивные доказательства с нулевым знанием Кэрол невозможно убедить, потому что она не участвует в интерактивном процессе протокол. Для убеждения Кэрол и других заинтересованных лиц нам нужен неинтерактивный протокол . Для неинтерактивных доказательств с нулевым знанием был придуман ряд протоколов [477, 198, 478, 197], которые не требуют непосредственного взаимодействия. Пегги может опубликовать их и, таким образом, док а- зать свое знание всем, у кого найдется время это проверить Базовый протокол похож на параллельное доказательство с нулевым знанием, но место Виктора занимает однонаправленная хэш-функция: (1) Пегги использует свою информацию и n случайных чисел для преобразования трудной проблемы в n раз- личных изоморфных проблем. Затем она с помощью своей информации и случайных чисел решает n но- вых трудных проблем. (2) Пегги вручает решение n новых трудных проблем. (3) Пегги использует все эти вручения в качестве входа для однонаправленной хэш-функции. (В конце концов эти вручения - не что иное, как строки битов.) Затем она сохраняет первые n битов полученного значения однонаправленной хэш-функции. (4) Пегги берет n битов, полученных на этапе (3). По очереди для каждой n-ой трудной проблемы она берет n-ый бит и (a) если бит равен 0, доказывает, что старая и новая проблемы изоморфны, либо (b) если бит равен 1, раскрывает решение, врученное на этапе (2), и доказывает, что оно является реш е- нием данной новой проблемы. (5) Пегги опубликовывает все решения, врученные на этапе (2), и все доказательства, полученные на этапе (4). (6) Виктор, Кэрол и все остальные заинтересованные лица проверяют, что этапы (1)-(5) выполнены правил ь- но. Это впечатляет: Пегги может опубликовать некоторые данные, которые не содержат никакой информации о ее секрете, но могут кого угодно убедить в существовании самого секрета . Этот протокол может быть использо- ван проверка определена как вычисление однонаправленной хэш-функции первоначальных сообщений и подп и- сываемого сообщения. Эта схема работает, потому что однонаправленная хэш-функция действует как беспристрастный генератор случайных битов. Чтобы мошенничать, Пегги нужно уметь предсказывать результат однонаправленной хэш- функции. (Помните, если решение трудной проблемы ей неизвестно , она может сделать на этапе (4) либо (a), либо (b), но не оба действия одновременно.) Если она каким-то образом узнает, выполнение какого действия потребует от нее однонаправленная хэш-функция, то она сможет смошенничать . Однако, Пегги не сможет за- ставить однонаправленную хэш-функцию выдать определенный бит или догадаться, какой бит будет получен . Однонаправленная хэш-функция по сути является заменителем Виктора в случайном выборе одного из двух доказательств на этапе (4). В неинтерактивном протоколе должно быть гораздо больше итераций в последовательности запрос/ответ . Пегги, а не Виктор, отбирает трудные проблемы с помощью случайных чисел . Она может подбирать различные проблемы, следовательно, и различные векторы вручения, до тех пор , пока хэш-функция не выдаст что-то, нуж- ное Пегги. В интерактивном протоколе 10 итераций - вероятность мошенничества Пегги составит 1 шанс из 2 10 (1 из 1024) - может быть достаточно. Однако, для неинтерактивных доказательств с нулевым знанием этого не хватит. Помните, что Мэллори всегда может выполнить на этапе (4) либо (a), либо (b). Он может, выполняя этапы (1)-(3), попытаться догадаться, что его попросят сделать, и посмотреть, правильно ли его предположение. Если нет, он попробует снова и снова. Сделать 1024 предположения на компьютере нетрудно. Для предотвращения такого вскрытия грубым взломом для неинтерактивных протоколов нужно 64 или даже 128 итераций. Главная идея состоит в использовании однонаправленной хэш-функции - Пегги не может предсказать выход хэш-функции, потому что она не может предсказать ее вход . Вручения, используемые на входе, становятся и з- вестны только после решения новых проблем . Общие замечания Блюм (Blum) доказал, что любая математическая теорема может быть преобразована в граф, такой, что д о- казательство теоремы будет эквивалентно доказательству существования гамильтонова цикла для этого графа . В общем виде то, что для любого NP-полного утверждения есть доказательство с нулевым знанием, использу ю- щее однонаправленные функции и, следовательно, хорошие алгоритмы шифрования, доказано в [620]. Любое математическое доказательство может быть преобразовано в доказательство с нулевым знанием . Используя эту методику, исследователь может доказать миру, что ему известно доказательство конкретной теоремы, не ра с- крывая самого решения. Блюм мог опубликовать свои результаты, не раскрывая их . Также существуют доказательства с минимальным раскрытием [590]. Для доказательства с минималь- ным раскрытием выполняются следующие свойства : 1. Пегги не может обмануть Виктора. Если Пегги не знает доказательства, ее шансы убедить Виктора в том, что доказательство ей известно, пренебрежимо малы. 2. Виктор не может обмануть Пегги. Он не получает ни малейшего намека на доказательство кроме того факта, что доказательство известно Пегги. В частности, Виктор не может продемонстрировать доказ а- тельство никому другому, не доказав все сам с самого начала. У доказательств с нулевым знанием есть дополнительное условие : 3. Виктор не узнает от Пегги ничего такого, чего он не смог бы узнать и самостоятельно кроме того фа к- та, что доказательство известно Пегги. Существует заметная математическая разница между доказательствами с минимальным раскрытием и док а- зательствами с нулевым знанием. Это различие находится вне рамок данной книги, но более искушенные чит а- тели могут проштудировать другую литературу. Понятия изложены в in [626, 619, 622]. Дальнейшая проработка этих идей, основанная на различных математических предположениях, выполнена в [240, 319, 239]. Существуют различные типы доказательств с нулевым знанием : — Совершенное. Существует имитатор, который создает стенограммы, полностью соответствующие реал ь- ным стенограммам (примеры с гамильтоновым ци клом и изоморфизмом графов). — Статистическое. Существует имитатор, который создает стенограммы, полностью соответствующие р е- альным стенограммам, кроме фиксированного числа исключений. — Вычислительное. Существует имитатор, который создает стенограммы, неотличимые от реальных. — Неиспользующее. Имитатора может и не быть, но мы можем доказать, что Виктор не узнает никакой информации из доказательства (параллельный пример) Годы тяжелой работы, как теоретической, так и прикладной, присели к появлению доказательств с мин и- мальным раскрытием и нулевым знанием . Майк Берместер (Mike Burmester) и Иво Десмедт изобрели широко- вещательно интерактивное доказательство, где владелец секрета может широковещательно передавать большой группе контролеров интерактивное доказательство с нулевым знанием [280]. Криптографы доказали, что все, что может быть доказано с помощью интерактивного доказательства, может быть доказано и с помощью инт е- рактивного доказательства с нулевым знанием [753, 137]. Хорошей обзорной статьей по данной теме является [548]. Дополнительные математические подробности, варианты, протоколы и приложения ищите в [590, 619, 240, 319, 620, 113,241, 152, 8, 660, 238, 591, 617, 510, 592, 214, 104, 216, 832, 97, 939, 622, 482, 615, 618, 215, 476, 71]. Много чего было написано по этому вопросу. 5.2 Использование доказательства с нулевым знанием для идентификации В реальном мире для доказательств подлинности часто используются физические символы: паспорта, вод и- тельские права, кредитные карточки и т.д. Эти символы содержат что-то, связывающее их с конкретным чел о- веком: обычно фотографию или подпись, но с той же вероятностью это может быть отпечаток пальца, снимок сетчатки глаза или рентгеновский снимок челюсти . Как было бы здорово делать что-то подобное цифровым образом? Использовать доказательства с нулевым знанием для доказательства идентичности было впервые предлож е- но Уриелем Файгом (Uriel Feige), Амосом Фиатом (Amos Fiat) и Ади Шамиром [566, 567]. Закрытый ключ Алисы становится функцией ее "идентичности" . Используя доказательство с нулевым знанием, она доказывает, что она знает свой закрытый ключ и, таким образом, свою идентичность . Соответствующие алгоритмы можно найти в разделе 23.11. Это очень многообещающая идея. Она позволяет человеку доказать свою личность без использования физ и- ческих символов. Однако, она не совершенна. Вот примеры возможных злоупотреблений . Проблема гроссмейстера Вот как Алиса, даже не зная правил шахмат, может обыграть гроссмейстера. (Иногда это называется про- блемой гроссмейстера.) Она посылает вызов Гарри Каспарову и Анатолию Карпову, предлагая играть в одно время, в одном и том же мести, но в раздельных комнатах . Она играет белыми против Каспарова и черными против Карпова. Ни один гроссмейстер не знает о другом. Карпов, играя белыми, делает свой ход первым . Алиса записывает ход и идет в комнату к Каспарову. Играя белыми, она делает тот же ход на доске Каспарова. Каспаров делает свой первый ход черными. Алиса запис ы- вает ход, идет в комнату к Карпову и делает тот же ход. Это продолжается, пока она не выигрывает одну из партий, проигрывая другую, или обе партии кончаются вничью . На самом деле Каспаров играет с Карповым, а Алиса просто посредник, повторяющий ходы одного грос с- мейстера на доске другого. Однако, если Карпов и Каспаров не знают о присутствии друг друга, каждый из них будет поражен игрой Алисы. Этот способ мошенничества может быть использовать против доказательства личности с нулевым знанием [485, 120]. Когда Алиса доказывает свою личность Мэллори, Мэллори может одновременно доказать Бобу, что он-то и есть Алиса. Обман, выполненный мафией Обсуждая свой протокол идентификации с нулевым знанием , Ади Шамир сказал [1424]: "Я могу ходить в принадлежащий мафии магазин хоть миллион раз подряд, а они все еще не смогут выдать себя за меня ." Вот как мафия сможет это сделать. Алиса ест в ресторанчике Боба, принадлежащем мафии . Кэрол делает покупки в дорогом ювелирном магазине Дэйва . Боб и Кэрол - мафиози, переговаривающиеся по потайному р а- диоканалу. Алиса и Дэйв не подозревают о мошенничестве . Когда Алиса поела и собралась платить и доказывать свою личность Бобу, Боб подает сигнал Кэрол, что п о- ра начинать. Кэрол выбирает бриллианты подороже и собирается доказывать свою личность Дэйву . Теперь, пока Алиса доказывает свою личность Бобу, тот подает сигнал Кэрол, и та выполняет тот же протокол с Дэйвом. Когда Дэйв задает вопрос по протоколу, Кэрол сообщает этот вопрос Бобу, а Боб задает его Алисе . Ко- гда Алиса отвечает, Боб передает правильный ответ Кэрол. По сути, Алиса просто доказывает свою личность Дэйву, а Боб и Кэрол просто, находясь внутри протокола, передают сообщения туда-сюда . Когда протокол за- вершается, Алиса доказала свою личность Дэйву и заплатила за дорогие бриллианты (с которыми Кэрол теперь и исчезнет). Обман, выполненный террористами Если Алиса хочет объединиться с Кэрол, то они также могут провести Дэйва. В этом протоколе Кэрол - и з- вестная террористка. Алиса помогает ей въехать в страну. Дэйв - офицер-пограничник, Алиса и Кэрол общаю т- ся по тайному радиоканалу. Когда Дэйв задает Кэрол вопросы в соответствии по протоколу с нулевым знанием, Кэрол передает их Ал и- се, которая и отвечает на вопросы. Кэрол повторяет эти ответы Дэйву. Carol recites these answers to Dave. По сути, Свою личность Дэйву доказывает Алиса, а Кэрол выступает в роли линии связи . Когда протокол заверша- ется, Дэйв считает, что Кэрол - это Алиса, и разрешает ей въехать в страну . Спустя три дня Кэрол всплывает у правительственного здания вместе с микроавтобусом, набитом взрывчаткой . Предлагаемые решения Оба описанных мошенничества возможны, так как заговорщики используют тайный радиоканал. Одним из способов предотвратить мошенничество является проведение процедуры идентификации в клетке Фарадея, бл о- кирующей электромагнитное излучение. В примере с террористом это гарантирует, что Кэрол не получит отв е- тов от Алисы. В примере с мафией Боб может построить фальшивую клетку Фарадея в своем ресторане, но у ювелира-то клетка будет работать , и Боб и Кэрол не смогут обмениваться сообщениями . Для решения пробле- мы гроссмейстера Алиса должна сидеть на своем стуле до конца игры . Тотас Бот (Thomas Both) и Иво Десмедт предложили другое решение, использующее точные часы [148]. Ес- ли каждый этап протокола должен происходить в заданное время, у мошенников не останется времени для о б- мена информацией. В случае с проблемой гроссмейстера это соответствует предложению ограничить время о б- думывания хода одной минутой - у Алисы не останется времени бегать из комнаты в комнату . В истории с ма- фией у Боб и Кэрол не хватит времени передавать друг другу ответы и вопросы . Обман с несколькими личностями Существуют и другие способы злоупотребить доказательствами идентичности с нулевым знанием, также рассматриваемые в [485, 120]. В ряде реализаций проверка при регистрации человеком своего ключа не прои з- водится. Следовательно, у Алисы может быть несколько закрытых ключей и, таким образом, несколько личн о- стей. Это может здорово помочь ей, если она захочет мошенничать с налогами . Алиса также может совершить преступление и скрыться. В первых, она создает несколько личностей, одна из которых не используется . Затем, она использует эту личность для совершения преступления так, чтобы свидетель идентифицировал ее как эту личность. Затем, она немедленно прекращает пользоваться этой личностью . Свидетель знает личность преступ- ника, но Алиса никогда больше не будет использовать эту личность - ее невозможно проследить . Для защиты от этого нужны механизмы, обеспечивающие, чтобы у каждого человека была только одна ли ч- ность. В [120] авторами предлагается причудливая идея защищенных от воровства детей, которые не могут быть клонированы, и у которых есть уникальный номер, являющийся частью их генетического кода . Они также предложили присваивать каждому ребенку личность при рождении . (Действительно, родителям придется сде- лать это, так как иначе ребенок может быть украден .) Этим тоже легко злоупотребить - родители могут создать для родившегося ребенка несколько личностей . В конце концов, уникальность личности основана на доверии . Прокат паспортов Алиса хочет поехать в Заир, но правительство этой страны не дает ей визы. Кэрол предлагает сдать свою личность Алисе "напрокат". (Первым это предложил Боб, но возник ряд очевидных проблем .) Кэрол продает Алисе свой закрытый ключ и Алиса едет в Заир, выдавая себя за Кэрол . Кэрол получает не только плату за свою личность, но и идеальное алиби. Она совершает преступление, пока |