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