Протокол аутентификации пользователей
- если $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$;
- если $\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 требует, чтобы противник мог сделать это лишь с пренебрежимо малой вероятностью.
Доказательство аутентичности в протоколах аутентификации пользователей по существу заключается в доказательстве пользователей знания своего секретного ключа без разглашения информации об этом ключе. Поэтому не удивительно, что для построения протоколов аутентификации пользователей можно использовать протоколы доказательства знания с нулевым разглашением.
Литература
- [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)