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


О решениях, принятых при определении асимптотической безопасности



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

О решениях, принятых при определении асимптотической безопасности 
При определении общего понятия асимптотической безопасности нами было при-
нято два решения: мы определили эффективные стратегии противника с помощью 
класса вероятностных полиноминально-временных алгоритмов и приравняли малые 
шансу на успех к пренебрежимо малым вероятностям. В некоторой мере, оба эти 
решения произвольны, и можно построить совершенно приемлемую теорию, назвав, 
скажем, эффективными стратегиями те, которые работают в квадратичном времени, 
или малой вероятностью на успех ту, что ограничена функцией 2−n. Тем не менее, мы 
кратко подтвердим нами принятые нами (стандартные) решения. 
Те, кто знаком с теорией сложности или со сложностью алгоритмов, осоз-
нают, что идея приравнивания эффективного вычисления к (вероятностным) 
полиномиально-временным алгоритмам характерна не только для криптогра-
фии. Достоинством использования (вероятностного) полиномиального време-
ни в качестве показателя эффективности является тот факт, что нам не нужно 
точно задавать вычислительную модель, поскольку в соответствии с тезисом 
Чёрча-Тьюринга все «приемлемые» вычислительные системы являются поли-
номиально эквивалентными. Таким образом, нам не приходится указывать, ис-
пользуем ли мы машину Тьюринга, булеву схему или машину с произвольным 
доступом к памяти. Мы можем представить алгоритмы, составленные с помо-
щью высокоуровневого псевдокода, и быть уверены, что эти алгоритмы будут 
работать в полиномиальном времени, как и любая их приемлемая реализация.
Другим достоинством (вероятностных) полиномиально-временных алго-
ритмов является то, что они соответствуют желаемым свойствам замыкания: 


60
в частности, алгоритм, полиномиально много раз обращающийся к полиноми-
ально-временной подпрограмме (и к тому же выполняющий только полиноми-
альные вычисления), сам будет работать в полиномиальном времени.
Наиболее важной характеристикой пренебрежимо малых вероятностей явля-
ется свойство замыкание, рассмотренное нами в предположении 3.6(2): прене-
брежимо малая функция, увеличенная в некоторое полиномиальное количество 
раз, остается пренебрежимо малой. В частности, это означает, что если алго-
ритм полиномиально много раз обращается к некоторой подпрограмме, которая 
каждый раз в результате такого обращения «терпит неудачу» с пренебрежимо 
малой вероятностью, то вероятность того, что какие-либо обращения к этой 
подпрограмме потерпят неудачу, остается пренебрежимо малой.


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




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

    Басты бет