Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Асимптотическая стойкость: Краткие выводы
| ПРЕДПОЛОЖЕНИЕ 3.6 Пусть negl1 и negl2 - это пренебрежимо малые
функции. Тогда, 1. Функция negl3, заданная с помощью negl3(n) = negl1(n)+negl2(n), является пренебрежимо малой. 2. Для любого положительного многочлена p, функция negl4, заданная с по- мощью negl4(n) = p(n) • negl1(n), является пренебрежимо малой. Вторая часть указанного выше предположения подразумевает, что если не- которое событие происходит в некотором эксперименте только с пренебрежимо малой вероятностью, тогда событие происходит с пренебрежимо малой веро- ятностью даже при повторении эксперимента полиномиально много раз. (Это основывается на границе объединения. См. Предположение A.7.) Например, вероятность того, что результатом n подбрасываний симметричной монеты бу- дет «орел», пренебрежимо мала. Это означает, что если мы повторим подбра- сывание n монет полиномиально много раз, вероятность того, что результатом любого из этих экспериментов будет n «орлов», остается пренебрежимо малой. Следствием второй части приведенного выше предположения является то, что если функция g не является пренебрежимо малой, тогда таковой не является ни одна из функций положительного многочлена p. Асимптотическая стойкость: Краткие выводы Каждое определение криптографической стойкости состоит из двух частей: определение того, что считается «взломом» системы, и конкретизация возмож- ностей противника. Возможности противника могут зависеть от многих фак- торов (например, в случае шифрования мы допускаем атаку на основе шифр- текста или подобранного открытого текста). Что же касается вычислительных возможностей противника, в дальнейшем мы будем создавать модель эффек- тивного противника и, таким образом, рассматривать только те стратегии про- тивника, которые могут быть осуществлены в вероятностно полиномиальном времени. Определения будут всегда формулироваться так, что взлом системы, происходящий с пренебрежимо малой вероятностью, не будет считаться зна- чительным. Таким образом, любое определение криптографической стойкости 59 будет подчиняться следующим общим принципам: Система является надежной, если для каждого вероятностного поли- номиально-временного противника A, осуществляющего атаку одного из формально заданных типов, вероятность успешного осуществления атаки противником A (если успех также формально задан) пренебрежимо мала. Такое определение является асимптотическим, потому что существует вероят- ность того, что при небольших значениях n противник с большой вероятностью добьется успеха. Для более подробного рассмотрения данного вопроса расширим понятие «пренебрежимо малый» с помощью следующего утверждения: Система является криптографически надежной, если для каждо- го ppt противника A, осуществляющего атаку некоторым формально заданным способом, и для каждого положительного многочлена p существует такое целое число N, что когда n > N, вероятность успеш- ной атаки A меньше 1/p(n). Обратите внимание, что никаких гарантий не дается для значений n ≤ N. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|