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

Система секретной связи совершенная

perfect secrecy system

Говоря неформально, система секретной связи в смысле теории Шеннона [1] называется совершенной, если перехват противником криптограммы не дает ему никакой дополнительной информации о зашифрованном сообщении. Это понятие было введено в основополагающей работе [1].

Пусть $((e_i\,|\, i\in K),\mathfrak K)$ — система секретной связи, где $e_i\colon M\to C$ для всех $i\in K$. Пусть также $\mathfrak M$ — некоторое априорное распределение вероятностей на пространстве сообщений $M$. Обозначим через $\widetilde k$ и $\widetilde m$ независимые случайные величины, имеющие распределения $\mathfrak K$ и $\mathfrak M$ соответственно. Вышеуказанная система секретной связи называется совершенной, если для любого сообщения $m\in M$ и любой криптограммы $c\in C$, имеющей ненулевую вероятность (т. е. такой, что $\Pr\left(e_{\widetilde k}(\widetilde m)=c\right)\ne0$) справедливо равенство $\Pr(\widetilde m=m)=\Pr\left(\widetilde m=m\,\left|\,e_{\widetilde k}(\widetilde m)=c\right.\right)$. Другими словами, условие совершенности означает, что при любой перехваченной криптограмме $c$ апостериорное распределение вероятностей на пространстве сообщений совпадает с априорным.

Система секретной связи совершенна тогда и только тогда, когда случайные величины $\widetilde m$ и $e_{\widetilde k}(\widetilde m)$ независимы. Условие совершенности эквивалентно также следующему условию: \[ \Pr\left(e_{\widetilde k}(m_1)=c\right)=\Pr\left(e_{\widetilde k}(m_2)=c\right)\quad\text{для любых }m_1,m_2\in\mathop{\mathrm{supp}}\mathfrak M,\, c\in C. \] Это условие показывает, что совершенность системы секретной связи зависит лишь от носителя распределения вероятностей $\mathfrak M$. В частности, если потребовать, чтобы $\mathop{\mathrm{supp}}\mathfrak M=M$, то условие совершенности либо выполняется при любом таком распределении, либо не выполняется ни при каком.

В совершенной системе секретной связи справедливо неравенство $\#\mathop{\mathrm{supp}}\mathfrak M\leqslant\#\mathop{\mathrm{supp}}\mathfrak K$. См. также [1].

Чистая система секретной связи, в которой имеется лишь один остаточный класс сообщений, совершенна для любого априорного распределения вероятностей на пространстве сообщений. В частности, такова система секретной связи Вернама. Для этой системы секретной связи приведенная выше нижняя оценка на $\#\mathop{\mathrm{supp}}\mathfrak K$ достигается при подходящем выборе $\mathfrak M$.

Литература

  • [1] Shannon, C. E. «Communication theory of secrecy systems» 1949

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