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

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

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

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

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

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

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

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

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

Литература[править]