Полиномиальная стойкость

polynomial security

В криптологии — одно из определений стойкости криптосистемы. Было введено для криптосистем вероятностного шифрования с открытым ключом. Полиномиальная стойкость определяется следующей угрозой. Противник, располагающий полиномиально ограниченными вычислительными ресурсами, выбирает два сообщения, $m_0$ и $m_1$ (одинаковой длины), и затем получает криптограмму сообщения $m_\sigma$, где бит $\sigma$ выбран случайным образом и неизвестен противнику. Требуется определить бит $\sigma$ с вероятностью, отделенной от $1/2$, т. е. не меньшей для всех достаточно больших $n$, чем $1/2+1/p(n)$, где $p$ — некоторый фиксированный полином, $n$ — параметр стойкости. Полиномиальная стойкость эквивалентна стойкости семантической.

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