Введение в современную криптографию



Pdf көрінісі
бет38/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   34   35   36   37   38   39   40   41   ...   249
Криптография Катц

ПРЕДПОЛОЖЕНИЕ 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 монет полиномиально много раз, вероятность того, что результатом 
любого из этих экспериментов будет «орлов», остается пренебрежимо малой.
Следствием второй части приведенного выше предположения является то, 
что если функция g не является пренебрежимо малой, тогда таковой не является 
ни одна из функций 
положительного многочлена p. 
Асимптотическая стойкость: Краткие выводы 
Каждое определение криптографической стойкости состоит из двух частей: 
определение того, что считается «взломом» системы, и конкретизация возмож-
ностей противника. Возможности противника могут зависеть от многих фак-
торов (например, в случае шифрования мы допускаем атаку на основе шифр-
текста или подобранного открытого текста). Что же касается вычислительных 
возможностей противника, в дальнейшем мы будем создавать модель эффек-
тивного противника и, таким образом, рассматривать только те стратегии про-
тивника, которые могут быть осуществлены в вероятностно полиномиальном 
времени. Определения будут всегда формулироваться так, что взлом системы, 
происходящий с пренебрежимо малой вероятностью, не будет считаться зна-
чительным. Таким образом, любое определение криптографической стойкости 


59
будет подчиняться следующим общим принципам:
Система является надежной, если для каждого вероятностного поли-
номиально-временного противника A, осуществляющего атаку одного из 
формально заданных типов, вероятность успешного осуществления атаки 
противником A (если успех также формально задан) пренебрежимо мала.
Такое определение является асимптотическим, потому что существует вероят-
ность того, что при небольших значениях n противник с большой вероятностью 
добьется успеха. Для более подробного рассмотрения данного вопроса расширим 
понятие «пренебрежимо малый» с помощью следующего утверждения:
Система является криптографически надежной, если для каждо-
го ppt противника A, осуществляющего атаку некоторым формально 
заданным способом, и для каждого положительного многочлена p 
существует такое целое число N, что когда n > N, вероятность успеш-
ной атаки A меньше 1/p(n).
Обратите внимание, что никаких гарантий не дается для значений n ≤ N.


Достарыңызбен бөлісу:
1   ...   34   35   36   37   38   39   40   41   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет