Криптографический протокол

Криптографический протокол — центральное понятие математической криптографии.

Рассмотрим, для простоты изложения, протоколы с двумя участниками, которых всюду будем называть Алисой и Бобом. Сначала нам потребуется определение интерактивной пары машин Тьюринга.

Пусть $(A,B)\,$ — пара машин Тьюринга, удовлетворяющих следующим требованиям:

• помимо обычных лент каждой из машин (в зависимости от модели это могут быть входные, выходные, рабочие и случайные ленты), они имеют еще общую коммуникационную ленту, доступную обеим машинам $A\,$ и $B\,$ как на чтение, так и на запись;
• перед началом работы на входных лентах машин $A\,$ и $B\,$ записаны входные слова $x_A\,$ и $x_B\,$ соответственно.
• на первом шаге активна машина $A\,$. Она выполняет некоторые (локальные) вычисления над своим входным словом $x_A\,$, записывает на коммуникационную ленту сообщение $m_1\,$ и переходит в специальное состояние, называемое состоянием ожидания;
• в этот момент активизируется машина $B\,$, которая выполняет вычисления над своим входным словом $x_B\,$ и полученным сообщением $m_1\,$, записывает на коммуникационную ленту сообщение $m_2\,$ и переходит в состояние ожидания, активизируя при этом машину $A\,$ и т. д.

Если на входе $(x_A, x_B)\,$ обе машины $A\,$ и $B\,$ останавливаются, то пусть $y_A\,$ и $y_B\,$ — слова, записанные на их выходных лентах соответственно. Говорят, что пара $(y_A,y_B)\,$ является результатом выполнения протокола $(A,B)\,$ на входе $(x_A,x_B)\,$. Если все взаимодействие между машинами состоит в посылке сообщения $m_1\,$ от $A\,$ к $B\,$, то такой протокол называется неинтерактивным. В противном случае протокол называется интерактивным. Количество раундов протокола $(A,B)\,$ — это количество сообщений, посланных машинами $A\,$ и $B\,$ друг другу. В частности, неинтерактивный протокол является однораундовым.

Машины $A\,$ и $B\,$ могут быть как детерминированными, так и вероятностными.

Задача, которую решает протокол $(A,B)\,$, а именно, вычисление $(y_A, y_B)\,$ по заданным $(x_A, x_B)\,$, является типичной для распределенных вычислений и не имеет, в таком общем виде, никакого криптографического содержания. Протокол становится криптографическим, если он решает одну из трех задач криптографии. Эти задачи состоят в обеспечении:

• конфиденциальности;
• целостности;
• неотслеживаемости.

Возможность формальной постановки этих задач и точного отделения криптографических протоколов от некриптографических представляет собой большую исследовательскую проблему.

Протоколы бывают следующими:

• прикладные (решают прикладные задачи)
• примитивы (используются для построения прикладных протоколов)

Литература

• Курс Н. П. Варновского. Основные понятия.