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] авторами предлагается причудливая идея защищенных от воровства детей, которые не могут быть клонированы, и у которых есть уникальный номер, являющийся частью их генетического кода. Они также предложили присваивать каждому ребенку личность при рождении. (Действительно, родителям придется сделать это, так как иначе ребенок может быть украден.) Этим тоже легко злоупотребить - родители могут создать для родившегося ребенка несколько личностей. В конце концов, уникальность личности основана на доверии.

Прокат паспортов

Алиса хочет поехать в Заир, но правительство этой страны не дает ей визы. Кэрол предлагает сдать свою личность Алисе "напрокат". (Первым это предложил Боб, но возник ряд очевидных проблем.) Кэрол продает Алисе свой закрытый ключ и Алиса едет в Заир, выдавая себя за Кэрол.

Кэрол получает не только плату за свою личность, но и идеальное алиби. Она совершает преступление, пока Алиса находится в Заире. "Кэрол" доказала свою личность в Заире, как она могла совершить преступление дома?

Конечно, развязаны руки и у Алисы. Она может совершить преступление либо перед отъездом, либо сразу же после возвращения, около дома Кэрол. Сначала она покажет, что она - Кэрол (имея закрытый ключ Кэрол, ей не составит труда сделать это), затем она совершит преступление и убежит. Полиция будет искать Кэрол. Кэрол будет утверждать, что сдала свою личность напрокат Алисе, но кто поверит в такую невероятную историю?

Проблема в том, что Алиса доказывает не свою личность, а то, что ей известна некоторая секретная информация. Именно связь между этой информацией и личностью и служит предметом злоупотребления. Решение защищенных от воровства детей защитило бы от такого мошенничества, как и создание полицейского государства, в котором все граждане должны очень часто доказывать свою личность (в конце дня, на каждом углу и т.д.). Помочь решить эту проблему могут биометрические методы - отпечатки пальцев, снимки сетчатки глаза, запись голоса и т.п.

Доказательство членства

Алиса хочет доказать Бобу, что она является членом суперсекретной организации, но не хочет раскрывать свою личность. Эта проблема, близкая проблеме доказательства личности, но отличающаяся от нее, была изучена в [887, 906, 907, 1201, 1445]. Ряд решений связан с проблемой групповых подписей (см. раздел 4.6).