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

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

block encryption system

Пусть $l$ — полиномиальный параметр. Система шифрования называется блоковой с длиной блока $l$, если ее пространством сообщений при произвольном значении $n$ параметра стойкости является $\{0,1\}^{l(n)}$. См. также система шифрования.

Пример 1 см. также [1]
Пусть $(f_{n,d}\,|\, n\in\mathbb N,\, d\in D_n)$ — сильно псевдослучайное полиномиально инвертируемое семейство перестановок, в котором $f_{n,d}$ — перестановка множества $\{0,1\}^{l(n)}$ (для всех $n\in\mathbb N$ и $d\in D_n$), где $l$ — полиномиальный параметр. Известно, что такие семейства существуют в предположении существования односторонних функций (см. семейство перестановок сильно псевдослучайное). Определим блоковую систему шифрования с секретным ключом и с длиной блока $l$ следующим образом. Алгоритм генерации ключей $\mathcal G$ на входе $1^n$, где $n\in\mathbb N$, выбирает $d\in_{\mathfrak U} D_n$ (для чего используется свойство доступности рассматриваемого семейства) и возвращает $(d,d)$. Алгоритм шифрования $\mathcal E$ на входе $(1^n,d,m)$, где $n\in\mathbb N$, $d\in D_n$ и $m\in\{0,1\}^{l(n)}$ вычисляет и возвращает $f_{n,d}(m)$ (здесь используется свойство полиномиальной вычислимости рассматриваемого семейства). Наконец, алгоритм расшифрования $\mathcal D$ на входе $(1^n,d,w)$, где $n\in\mathbb N$, $d\in D_n$ и $w\in\{0,1\}^{l(n)}$ вычисляет и возвращает $f_{n,d}^{-1}(m)$ (здесь используется свойство полиномиальной инвертируемости рассматриваемого семейства). Тогда нетрудно показать (см. [1]), что построенная система шифрования является стойкой в следующем смысле. Пусть $d\in_{\mathfrak U} D_n$, где $n\in\mathbb N$ — параметр стойкости. Атака заключается в том, что противник (разумеется, не знающий $d$) имеет доступ к оракулам, вычисляющим функции $f_{n,d}$ и $f_{n,d}^{-1}$. Другими словами, противник может получить как шифртекст для любого сообщения из $\{0,1\}^{l(n)}$, так и сообщение, соответствующее любому шифртексту из $\{0,1\}^{l(n)}$. В конце атаки противник должен выбрать пару $(m_0,m_1)$ сообщений из $\{0,1\}^{l(n)}$, которые ранее не были ни выбраны им для получения шифртекста, ни получены в качестве сообщения, соответствующего выбранному шифртексту. Затем противник получает шифртекст для сообщения $m_b$, где $b\in_{\mathfrak U}\{0,1\}$ (т. е. $f_{n,d}(m_b)$), но не сам бит $b$. После этого противник должен угадать бит $b$ (в чем и состоит угроза). Утверждение о стойкости заключается в том, что если $A$ — произвольный противник вышеуказанного вида, моделируемый полиномиальным вероятностным алгоритмом, и $\sigma_A(n)$ — вероятность нахождения этим противником бита $b$ после описанной атаки, то для любого полинома $p$ неравенство $\sigma_A(n)\leqslant1/2+1/p(n)$ выполняется при всех достаточно больших $n\in\mathbb N$.

Литература

  • [1] Luby, M. «Pseudorandomness and cryptographic applications» 1996

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