Список обозначений

Протокол аутентификации пользователей

user authentication protocol
Синонимы: протокол идентификации пользователей
Определение 1 протокол аутентификации пользователей; см. также [1]
Протокол аутентификации пользователей состоит из полиномиального вероятностного алгоритма $\mathcal G$ и пары интерактивных полиномиальных вероятностных алгоритмов $(\mathcal P,\mathcal V)$, удовлетворяющих следующим условиям:
  1. если $w\in\{0,1\}^*$, то $\mathop{\mathrm{supp}}\mathcal G(w)\subseteq\{0,1\}^*\times\{0,1\}^*$, причем для любой пары $(x,y)\in\mathop{\mathrm{supp}}\mathcal G(w)$ всегда выполняется равенство $\langle{\mathcal P(x),\mathcal V}\rangle(w,y)=1$;
  2. если $\mathcal P’$ и $\mathcal V’$ — интерактивные полиномиальные от длины общего входа вероятностные алгоритмы, то величина \[ \max_{z\in\{0,1\}^*,\, w\in\{0,1\}^n}\Pr(\langle{\mathcal P'(z,\langle{\mathcal P(x),\mathcal V'(z)}\rangle_*(w,y)),\mathcal V}\rangle(w,y)=1) \] пренебрежимо мала как функция от $n\in\mathbb N$, где $(x,y)\leftarrow\mathcal G(w)$, а $\langle{\cdot,\cdot}\rangle_*$ отличается от $\langle{\cdot,\cdot}\rangle$, тем, что совместное вычисление может повторяться полиномиальное от длины общего входа число раз.

Схема применения протокола аутентификации пользователей из определения 1 может выглядеть следующим образом. Пусть имеется сеть связи, идентификаторы всех пользователей которой являются строками из $\{0,1\}^n$, где $n\in\mathbb N$ — параметр стойкости. Предполагается, что каждый пользователь сгенерировал пару $(x,y)\leftarrow\mathcal G(w)$, где $w$ — идентификатор этого пользователя. В этой паре $x$ и $y$ — соответственно секретный и открытый ключи пользователя; $x$ хранится пользователем в секрете, а $y$ публикуется. Алгоритм $\mathcal G$ называется алгоритмом генерации ключей.

Алгоритмы $\mathcal P$ и $\mathcal V$ используются собственно для аутентификации пользователей. При этом пользователь, доказывающий свою аутентичность, выполняет алгоритм $\mathcal P$, а пользователь, проверяющий это доказательство — алгоритм $\mathcal V$. После совместного вычисления доказывающего и проверяющего последний либо принимает доказательство (если алгоритм $\mathcal V$ возвращает на выходе $1$) аутентичности, либо отвергает это доказательство (в противном случае). Условие 1 определения 1, называемое в [1] жизнеспособностью (viability), означает, что доказательство аутентичности честного доказывающего всегда принимается честным проверяющим. Условие 2 определения 1, называемое в [1] просто стойкостью (security), является формализацией стойкости протокола аутентификации пользователей в следующем смысле. Противник, обладающий полиномиально ограниченными вычислительными ресурсами и имеющий изначально некоторую априорную информацию $z$, сначала взаимодействует (возможно, несколько раз) с честным доказывающим (имеющим идентификатор $w$, секретный ключ $x$ и открытый ключ $y$), выступая в качестве проверяющего. При этом он получает информацию $\langle{\mathcal P(x),\mathcal V’(z)}\rangle_*(w,y)$. Затем противник пытается пройти аутентификацию в качестве этого доказывающего, взаимодействуя с честным проверяющим. Условие 2 определения 1 требует, чтобы противник мог сделать это лишь с пренебрежимо малой вероятностью.

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

Пример 2 см. также [1]
Пусть $f$ — односторонняя функция. Предположим, что алгоритм $\mathcal G$ на входе $w\in\{0,1\}^*$ выбирает $x\in_{\mathfrak U}\{0,1\}^{\lvert{w}\rvert}$ и возвращает $(x,f(x))$. В качестве пары интерактивных алгоритмов $(\mathcal P,\mathcal V)$ выберем протокол доказательства знания для $\mathrm{NP}$-отношения $\{(f(v),v)\,|\, v\in\{0,1\}^*\}$ с пренебрежимо малой ошибкой и вычислительно нулевым разглашением в модели с дополнительными входами. Такой протокол существует в предположении существования односторонних функции в неоднородной модели вычислений. Тогда алгоритм $\mathcal G$ и пара интерактивных алгоритмов $(\mathcal P,\mathcal V)$ образуют протокол аутентификации пользователей. Таким образом, протоколы аутентификации пользователей существуют в предположении существования произвольных односторонних функций в неоднородной модели вычислений.

Литература

  • [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна