Опишем один из простейших протоколов подбрасывания монеты по телефону (так называемая схема Блюма-Микали).

Для его реализации у абонентов A и B должна быть односторонняя функция f: X→Y, удовлетворяющая следующим условиям:

1) X — конечное множество целых чисел, которое содержит одинаковое количество четных и нечетных чисел;

2) любые числа x1,x2∈X, имеющие один образ f(x1)=f(x2), имеют одну чётность;

3) по заданному образу f(x) «трудно» вычислить четность неизвестного аргумента x.

Роль подбрасывания монеты играет случайный и равновероятный выбор элемента x∈X, а роль орла и решки — четность и нечетность xсоответственно.

Пусть A — абонент, подбрасывающий монету, а B — абонент, угадывающий результат.

Протокол состоит из следующих шагов:

1) Aвыбирает x («подбрасывает монету»), зашифровывает x, т.е. вычисляет y=f(x), и посылает yабоненту B;

2) B получает y, пытается угадать четность xи посылает свою догадку абоненту A;

3) Aполучает догадку от B и сообщает B, угадал ли он, посылая ему выбранное число x;

4) B проверяет, не обманывает ли A, вычисляя значение f(x) и сравнивая его с полученным на втором шаге значением y.

3. Взаимодействуют два абонента A и B (типичный пример: A — клиент банка, B — банк). Абонент A хочет доказать абоненту B, что он именно A, а не противник.

Протокол решения этой задачи принято называть протоколом идентификации абонента.

4. Взаимодействуют несколько удаленных абонентов, получивших приказы из одного центра. Часть абонентов, включая центр, могут быть противниками. Необходимо выработать единую стратегию действий, выигрышную для абонентов.

Эту задачу принято называть задачей о византийских генералах, а протокол ее решения — протоколом византийского соглашения.

Опишем пример, которому эта задача обязана своим названием.

Византия. Ночь перед великой битвой. Византийская армия состоит из nлегионов, каждый из которых подчиняется своему генералу. Кроме того, у армии есть главнокомандующий, который руководит генералами. Однако империя находится в упадке и до одной трети генералов, включая главнокомандующего, могут быть предателями.

В течение ночи каждый из генералов получает от главнокомандующего приказ о действиях на утро, причем возможны два варианта приказа: «атаковать» или «отступать».

Варианты исхода боя:

1. Если все честные генералы атакуют, то они побеждают.

2. Если все они отступают, то им удается сохранить армию.

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