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

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

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

Пусть $(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})\,$, является типичной для распределенных вычислений и не имеет, в таком общем виде, никакого криптографического содержания. Протокол становится криптографическим, если он решает одну из трех задач криптографии. Эти задачи состоят в обеспечении:

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

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

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

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

Литература

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