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

Система шифрования

encryption system
Синонимы: криптосистема, шифр
Определение 1 система шифрования; см. также [1]
Предположим, что каждому числу $n\in\mathbb N$ (играющему роль параметра стойкости) поставлено в соответствие множество $M_n\subseteq\{0,1\}^*$, называемое пространством сообщений или пространством открытых текстов при данном $n$. Системой шифрования называется тройка полиномиальных вероятностных алгоритмов $(\mathcal G,\mathcal E,\mathcal D)$, называемых алгоритмами генерации ключей, шифрования и расшифрования соответственно, таких, что
  1. $\mathop{\mathrm{supp}}\mathcal G(1^n)\subseteq\{0,1\}^*\times\{0,1\}^*$ для любого $n\in\mathbb N$;
  2. при всех $m\in M_n$, $(e,d)\in\mathop{\mathrm{supp}}\mathcal G(1^n)$ ($n\in\mathbb N$) всегда выполняется равенство $\mathcal D(1^n,d,\mathcal E(1^n,e,m))=m$.

Схема применения системы шифрования из определения 1 может выглядеть следующим образом. Пусть $n$ — параметр стойкости и $(e,d)\leftarrow\mathcal G(1^n)$ (см. условие 1 определения 1). Здесь ключ $e$ служит для шифрования сообщений, а ключ $d$ — для их расшифрования. Если $e$ публикуется, а $d$ хранится получателем в секрете, то система шифрования называется системой с открытым ключом. В этом случае шифровать произвольные сообщения может каждый, в том числе и противник. Если же $d=e$ является общим секретным ключом отправителя и получателя, то система шифрования называется системой с секретным ключом. Чтобы конфиденциально передать сообщение $m\in M_n$, отправитель вычисляет шифртекст $w\leftarrow\mathcal E(1^n,e,m)$ и посылает $w$ получателю. Получатель, получив шифртекст $w$ от отправителя, может восстановить исходное сообщение $m$ как $\mathcal D(1^n,d,w)$ (см. условие 2 определения 1).

В дальнейшем в этой статье мы предполагаем, что $M_n=\{0,1\}^*$ для всех $n\in\mathbb N$. Если же $M_n=\{0,1\}^{l(n)}$ при любом $n\in\mathbb N$, где $l$ — полиномиальный параметр, то система шифрования называется блоковой с длиной блока $l$.

Среди видов стойкости систем шифрования наиболее важны семантическая стойкость (являющаяся аналогом совершенности для систем секретной связи в смысле теории Шеннона) и стойкость, основанная на вычислительной неотличимости шифртекстов (являющаяся аналогом полиномиальной стойкости из работы [2]). Мы определим версии этих видов стойкости для многих сообщений; версии для одного сообщения получаются, если в нижеследующих определениях 2 и 3 считать полиномиальный параметр $t$ не произвольным, а тождественно равным $1$.

Определение 2 семантическая стойкость для многих сообщений; см. также [1]
Система шифрования с открытым ключом $(\mathcal G,\mathcal E,\mathcal D)$ называется семантически стойкой для многих сообщений, если для любых полиномиальных параметров $t$ и $l$ и любого полиномиального вероятностного алгоритма $\mathcal A$ существует полиномиальный вероятностный алгоритм $\mathcal B$ такой, что для любого полиномиально конструируемого семейства распределений вероятностей $(\mathfrak X_n\,|\, n\in\mathbb N)$, в котором $\mathop{\mathrm{supp}}\mathfrak X_n\subseteq\left(\{0,1\}^{l(n)}\right)^{t(n)}$ при всех $n\in\mathbb N$, любой полиномиально вычислимой функции $h\colon\{0,1\}^*\to\{0,1\}^*$, любой функции $f\colon\{0,1\}^*\to\{0,1\}^*$ и любого полинома $p$ неравенство \begin{align*} &\Pr\left(\mathcal A\left(1^n,e,\overline{\mathcal E}(1^n,e,\overline x),h(1^n,\overline x)\right)=f(1^n,\overline x)\right)\\&\qquad\leqslant\Pr(\mathcal B(1^n,h(1^n,\overline x))=f(1^n,\overline x))+\frac1{p(n)}, \end{align*} где $(e,\cdot)\leftarrow\mathcal G(1^n)$, $\overline x=\left(x_1,\dots,x_{t(n)}\right)\leftarrow\mathfrak X_n$ ($x_i\in\{0,1\}^{l(n)}$), $\overline{\mathcal E}(1^n,e,\overline x)=\left(\mathcal E(1^n,e,x_1),\dots,\mathcal E\left(1^n,e,x_{t(n)}\right)\right)$, выполняется при всех достаточно больших $n\in\mathbb N$. Определение системы шифрования с секретным ключом, семантически стойкой для многих сообщений, получается из этого определения посредством исключения $e$ из входных данных алгоритма $\mathcal A$.
Определение 3 неотличимость шифртекстов для многих сообщений; см. также [1]
Система шифрования с открытым ключом $(\mathcal G,\mathcal E,\mathcal D)$ удовлетворяет условию неотличимости шифртекстов для многих сообщений, если для любых полиномиальных параметров $t$ и $l$ и любого полиномиально конструируемого семейства случайных величин \[ \left(\left.\left(\left(\widetilde x_{n,1},\dots,\widetilde x_{n,t(n)}\right),\left(\widetilde y_{n,1},\dots,\widetilde y_{n,t(n)}\right),\widetilde z_n\right)\,\right|\,n\in\mathbb N\right), \] в котором $\widetilde x_{n,i}$ и $\widetilde y_{n,i}$ принимают значения в множестве $\{0,1\}^{l(n)}$ при всех $i\in\{1,\dots,t(n)\}$ и $n\in\mathbb N$, семейства случайных величин \[ \left(\left.\left(\widetilde e_n,\widetilde z_n,\left(\mathcal E(1^n,\widetilde e_n,\widetilde x_{n,1}),\dots,\mathcal E\left(1^n,\widetilde e_n,\widetilde x_{n,t(n)}\right)\right)\right)\,\right|\,n\in\mathbb N\right) \] и \[ \left(\left.\left(\widetilde e_n,\widetilde z_n,\left(\mathcal E(1^n,\widetilde e_n,\widetilde y_{n,1}),\dots,\mathcal E\left(1^n,\widetilde e_n,\widetilde y_{n,t(n)}\right)\right)\right)\,\right|\,n\in\mathbb N\right) \] где $(\widetilde e_n,\cdot)=\mathcal G(1^n)$, вычислительно неотличимы. Для системы шифрования с секретным ключом условие неотличимости шифртекстов для многих сообщений получается из этого условия посредством исключения $\widetilde e$ из определения семейств случайных величин, которые должны быть вычислительно неотличимыми.

Отметим, что случайные величины $\widetilde x_{n,1},\dots,\widetilde x_{n,t(n)},\widetilde y_{n,1},\dots,\widetilde y_{n,t(n)},\widetilde z_n$ из определения 3, вообще говоря, зависимы. Случайная величина $\widetilde z_n$ из этого определения играет роль априорной информации о сообщениях $\widetilde x_{n,1},\dots,\widetilde x_{n,t(n)}$ и $\widetilde y_{n,1},\dots,\widetilde y_{n,t(n)}$. Например, она может быть равна \begin{equation}\label{e:znspecialcase} \left(\left(\widetilde x_{n,1},\dots,\widetilde x_{n,t(n)}\right),\left(\widetilde y_{n,1},\dots,\widetilde y_{n,t(n)}\right)\right). \end{equation}

Теорема 4 см. также [1]
Следующие условия для системы шифрования (с открытым или секретным ключом) эквивалентны:
  1. семантическая стойкость для многих сообщений;
  2. семантическая стойкость для многих сообщений в частном случае, когда функция $f$ из определения 2 полиномиально вычислима;
  3. условие неотличимости шифртекстов для многих сообщений;
  4. условие неотличимости шифртекстов для многих сообщений в частном случае, когда случайная величина $\widetilde z_n$ из определения 3 имеет вид \eqref{e:znspecialcase} для любого $n\in\mathbb N$.
Кроме того, для системы шифрования с открытым ключом любое из этих условий эквивалентно условию неотличимости шифртекстов для одного сообщения.
Отметим, что если существуют псевдослучайные генераторы (что верно тогда и только тогда, когда существуют односторонние функции — см. генератор псевдослучайный), то можно построить систему шифрования с секретным ключом, которая удовлетворяет условию неотличимости шифртекстов для одного сообщения, но не для многих сообщений (см. [1]).

Литература

  • [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)
  • [2] Goldwasser, S. and Micali, S. «Probabilistic encryption» 1984

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