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

Материал из Циклопедии
Перейти к: навигация, поиск

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

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

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

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

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

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

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

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

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

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

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

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

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты