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



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

3.1.2 Асимптотический подход 
Как уже отчасти было сказано выше, существуют некоторые технические и 
теоретические сложности, связанные с использованием конкретного подхода в 
вопросах стойкости системы. Эти вопросы должны решаться на практике, но 
если конкретная стойкость не является безотлагательной проблемой, удобнее 
использовать асимптотический подход к стойкости. Именно такой подход и 
применяется в данной книге. Этот подход, уходящий своими корнями в теорию 
сложности, вводит целочисленный параметр безопасности n, который параме-
тризует криптографические системы, а также задействованные стороны: чест-
ных участников и перехватчика. Когда честные участники запускают систему 
(т.е. генерируют ключи), они выбирают некоторое значение n в качестве пара-
метра безопасности. В целях настоящего обсуждения условимся, что параметр 
безопасности соответствует длине ключа. Допустим, что параметр безопасно-
сти известен противнику, атакующему систему, теперь мы рассматриваем вре-
мя работы противника, а также вероятность успеха, поскольку функции пара-
метра вероятности больше функций конкретных чисел. Тогда :
1. Мы приравниваем «эффективных противников» к случайным (т.е. вероятност-
ным) алгоритмам, работающим в течение полиномиального времени от n. Это зна-
чит, что существует некоторый многочлен p, такой что противник работает в течение 
максимум p(n), когда параметр безопасности равен n. Для реальной эффективности 
нам также необходимо, чтобы честные участники тоже действовали в полиноми-
альном времени, однако, подчеркнем, что противник может обладать большими 
возможностями (и действовать значительно дольше), чем честные участники.
2. Мы приравниваем понятие «малая вероятность успеха» к вероятности 
успеха меньше, чем любой обратный многочлен от n (см. Определение 3.4). 


55
Такие вероятности называются пренебрежимо малыми.
Пусть ppt означает «вероятностное полиномиальное время». Тогда определе-
ние асимптотической стойкости примет следующую общую форму:
Система является надежной, если любой ppt противник может взло-
мать систему с пренебрежимо малой вероятностью.
Такое понятие безопасности является асимптотичным, поскольку безопас-
ность зависит от поведения системы при достаточно больших значениях n. По-
ясним это с помощью следующего примера.


Достарыңызбен бөлісу:
1   ...   30   31   32   33   34   35   36   37   ...   249




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

    Басты бет