Введение в современную криптографию
Асимптотический подход в деталях
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Асимптотический подход в деталях
Теперь мы более формально рассмотрим понятия «алгоритмы полиномиаль- ного времени» и «пренебрежительно малая вероятность успеха». Эффективные алгоритмы . Мы определили, что алгоритм является эффектив- ным, если работает в течение полиномиального времени. Алгоритм A работает в течение полиномиального времени, если существует многочлен p, такой что для каждого ввода x ∈ {0, 1}* вычисление A(x) оканчивается за максимум p(|x|) ша- гов. (Здесь |x| обозначает длину строки x.) Как было сказано ранее, нас интере- суют только противники, работающие в полиномиальном времени от параметра безопасности n. Поскольку мы измеряем время работы алгоритма с точки зрения длины входных данных, иногда мы предоставляем алгоритмам параметр безо- пасности, записанный в унарном виде (т. е. 1n или строка из n единиц), в качестве входных данных. Стороны, точнее, алгоритмы, которые они используют, помимо параметра безопасности могут использовать другие входные данные (например, сообщение, которое необходимо зашифровать), и мы допускаем, что они работа- ют в полиномиальном времени от (общей) длины входных данных. По умолчанию мы допускаем, что все алгоритмы являются вероятностными (или случайными). Каждый такой алгоритм может «подбрасывать монетку» на каждом этапе своей работы. Иными словами, алгоритм на каждом этапе имеет 57 доступ к по-настоящему произвольным битам. Аналогичным образом, мы можем рассматривать случайный алгоритм, как тот, которому помимо входных данных за- дана равномерно распределенная случайная лента достаточной длины1, чьи биты он может использовать в своей работе по мере необходимости. Существуют две причины, по которым мы по умолчанию рассматриваем случайные алгоритмы. Во-первых, случайность существенна для криптографии (например, при выборе случайных ключей и т.д .), поэтому честные участники должны быть вероятност- ными, исходя из чего естественно допускать, что и противники тоже могут быть вероятностными. Во-вторых, рандомизация практична и, насколько нам известно, наделяет перехватчиков дополнительной мощностью. Поскольку нашей целью яв- ляется создание модели всех реалистичных атак, мы предпочитаем более свобод- ное определение эффективного вычисления. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|