Сергей Дориченко - 25 этюдов о шифрах

Опишем пример, которому эта задача обязана своим названием. Византия. Ночь перед великой битвой. Византийская армия состоит из n легионов, каждый из которых подчиняется своему генералу. Кроме того, у армии есть главнокомандующий, который руководит генералами. Однако империя находится в упадке и до одной трети генералов, включая главнокомандующего, могут быть предателями. В течение ночи каждый из генералов получает от главнокомандующего приказ о действиях на утро, причем возможны два варианта приказа: «атаковать» или «отступать». Если все честные генералы атакуют, то они побеждают. Если все они отступают, то им удается сохранить армию. Но если часть из них атакует, а часть отступает, то они терпят поражение. Если главнокомандующий окажется предателем, то он может дать разным генералам разные приказы, поэтому приказы главнокомандующего не стоит выполнять беспрекословно. Если каждый генерал будет действовать независимо от остальных, результаты могут оказаться плачевными. Очевидно, что генералы нуждаются в обмене информацией друг с другом (относительно полученных приказов) с тем, чтобы прийти к соглашению.

Осмысление различных протоколов и методов их построения привело в 1985–1986 гг. к появлению двух плодотворных математических моделей — интерактивной системы доказательства и доказательства с нулевым разглашением .

Математические исследования этих новых объектов позволили доказать несколько утверждений, весьма полезных при разработке криптографических протоколов.

Под интерактивной системой доказательства ( P , V , S ) понимают протокол взаимодействия двух абонентов: P (доказывающий) и V (проверяющий). Абонент P хочет доказать V , что утверждение S истинно. При этом абонент V самостоятельно, без помощи P , не может доказать утверждение S (поэтому V и называется проверяющим). Абонент P может быть и противником, который хочет доказать V , что утверждение S истинно, хотя оно ложно. Протокол может состоять из многих раундов обмена сообщениями между P и V и должен удовлетворять двум условиям:

1) полнота — если S действительно истинно, то абонент P почти наверняка убедит абонента V признать это;

2) корректность — если S ложно, то абонент P вряд ли убедит абонента V , что S истинно.

Здесь словами «почти наверняка» и «вряд ли» мы заменили точные математические формулировки, использующие понятие вероятности.

Подчеркнем, что в определении системы ( P , V , S ) не допускалось, что V может быть противником. А если V оказался противником, который хочет «выведать» у P какую-нибудь новую полезную для себя информацию об утверждении S ? В этом случае P , естественно, может не хотеть, чтобы это случилось в результате работы протокола ( P , V , S ). Протокол ( P , V , S ), решающий такую задачу, называется доказательством с нулевым разглашением и должен удовлетворять, кроме условий 1 и 2, еще и следующему условию:

3) нулевое разглашение (или стойкость) — в результате работы протокола ( P , V , S ) абонент V не увеличит свои знания об утверждении S или, другими словами, не сможет извлечь никакой информации о том, почему S истинно.

Самое удивительное, что в 1991 году для широкого класса математических проблем (включающего так называемые NP-полные задачи ) удалось доказать существование доказательств с нулевым разглашением. Впрочем, это доказано только в предположении, что существует односторонняя функция.

Приведем одно практическое применение теории доказательств с нулевым разглашением — «интеллектуальные карточки» (неподделываемые удостоверения личности, кредитные карточки и т.п.). В них вмонтирован микропроцессор, реализующий действия абонента P в протоколе, претендующем быть протоколом доказательства с нулевым разглашением ( P , V , S ). Здесь абонент P — владелец карточки, а абонент V — например, компьютер в банке или в проходной секретного учреждения. Подумайте, почему в таком случае можно обеспечить неподделываемость удостоверений личности и кредитных карточек.

Вы прочли первую книгу по криптографии.

Если вам хочется подробней узнать историю криптографии, события и легенды, связанные с ней, то рекомендуем попытаться найти и прочесть упомянутые в этюде 1.4 книги Д. Кана и Т.А. Соболевой, а также любые номера журнала «Cryptology».