Введение в криптографию
[an error occurred while processing this directive]

Доказательства с нулевым разглашением - часть 5


Предположим, например, что Алиса - это интеллектуальная банковская карточка, в которой реализован алгоритм P, а Боб - это компьютер банка, выполняющий программу V. Прежде чем начать выполнение каких-либо банковских операций, банк должен убедиться в подлинности карточки и идентифицировать ее владельца, или, говоря на языке криптографии, карточка должна пройти аутентификацию. В принципе для этой цели можно использовать приведенный выше протокол IG. В этом случае в памяти банковского компьютера хранится пара графов , сопоставленная Алисе, а на интеллектуальной карточке - та же пара графов и изоморфизм . Предполагается, что, кроме Алисы, этот изоморфизм никто не знает (кроме, быть может, Боба) и поэтому с помощью протокола IG карточка доказывает свою аутентичность. При этом свойство полноты означает, что карточка наверняка докажет свою аутентичность. Свойство корректности защищает интересы банка от злоумышленника, который, не являясь клиентом банка, пытается пройти аутентификацию, используя фальшивую карточку. Свойство нулевого разглашения защищает клиента от злоумышленника, который, подслушав одно или более выполнений протокола аутентификации данной карточки, пытается пройти аутентификацию под именем Алисы. Конечно, в данном случае бессмысленно доказывать, что пара графов принадлежит языку ИЗОМОРФИЗМ ГРАФОВ, поскольку она заведомо выбирается из этого языка. Вместо этого Алиса доказывает, что она знает изоморфизм . Интерактивные доказательства такого типа называются доказательствами знания.

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

Next: Литература к главе 2

Up: 2. Криптография и теория

Previous: 2.4. Псевдослучайные генераторы

Contents:




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]