Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Пренебрежимо малая функция стремится к нулю быстрее, чем ^jy» где р(п) — произвольный полином. Если неполиномиально ограниченная величина считается недостижимой (например, при выделении ресурсов), то можно совершенно безопасно пренебречь любой величиной, обратной к ней.
Рассмотрим несколько примеров.
166
Часть II. Математические основы
Вероятность
Prob["Prime_Gen(lfc) — не простое число"] пренебрежимо мала, а вероятность
1 — Prob["Prime_Gen(lfc) — не простое число"] =
= Prob["Prime_Gen(lfc) — простое число"]
является огромной.
Вернемся к примеру 3.6. Если число р является простым и состоит из к бит (число q = также является простым), можно пренебречь величиной -—^ и получить приближенную оценку РгоЬ[Л] га |.
В заключение заметим, что если величина не является пренебрежимо малой, то ее часто называют значимой (significant quantity). Например, в ряде примеров, посвященных задачам принятия решений, принадлежность которых классу W можно эффективно проверить, существует значимая вероятность того, что при простом случайном выборе из пространства вычислительных деревьев (рис. 4.4) мы найдем свидетельство, позволяющее подтвердить ее принадлежность классу^.
4.7 Полиномиальная неразличимость
В предыдущем разделе мы показали, что пренебрежимо малые величины мож- i но игнорировать. Однако в некоторых ситуациях мы, наоборот, вынуждены отказаться от попыток игнорировать определенные величины.
В качестве примера рассмотрим два эксперимента в пространстве больших нечетных составных чисел фиксированной длины. Обозначим первый эксперимент как ?2_Рпте, а второй — ?з prime- В ходе этих экспериментов генерируются большие случайные целые числа одинакового размера: в эксперименте Ь'грнте порождаются произведения двух разных больших простых множителей, а в эксперименте Езр^ — трех и больше. Затем испытуемому предъявляется некое целое число N, порожденное одним из этих экспериментов. Можно ли уверенно определить, в результате которого из двух экспериментов появилось число TV? (Напомним, что в ходе эксперимента -E^Pnme и ?з_Рпте генерируются целые числа одинакового размера.)
По определению 3.5 (раздел 3.5) результатом таких экспериментов являются случайные величины, зависящие от случайных операций. Случайные величины, порожденные в ходе экспериментов Егрпте и -Ез_Рпте> имеют совершенно разные распределения: эксперимент .Esj'rime генерирует произведение двух простых
Глава 4. Вычислительная сложность
167
множителей с вероятностью 1, а эксперимент ?з_Рпте — нет. Однако различить целые числа, возникшие в результате этих экспериментов, очень трудно.
Дадим точное определение неразличимых ансамблей (indistinguishable ensembles), или неразличимых экспериментов (indistinguishable experiments).
Определение 4.14 (Классификатор ансамблей). Пусть Е = {е±, е2, ¦ ¦¦} и Е' = = {е^, е'2, ¦ ¦ -} — два множества ансамблей, в которых eiue^ — случайные величины из конечного выборочного пространства S. Введем обозначение k = log2 Пусть а = (а\, а2,..., ае) — вектор, состоящий из случайных переменных, которые все порождены в результате либо эксперимента Е, либо эксперимента Е', где ? — величина, ограниченная полиномом, зависящим от аргумента к.
Классификатор (distinguisher) Т> пары (Е,Е') представляет собой вероятностный алгоритм, завершающий работу за время, ограниченное полиномом, зависящим от аргумента к. Результат работы алгоритма Т> принадлежит множеству {0,1} и удовлетворяет следующим условиям: 1) *D(a, Е) = 1 тогда и только тогда, когда вектор а принадлежит множеству Е; и 2) Т)(а, Е') = 1 тогда и только тогда, когда вектор а принадлежит множеству Е'.
Будем говорить, что классификатор Т> различает пару (Е, Е') с преимуществом (advantage) Adv > 0, где
Adv(P) =| Pvob[V(a,E) = 1] - Prob[P(a, ??) - 1] | .
Следует подчеркнуть, что в определении преимущества классификатора Т> используются распределения вероятностей: классификатор является вероятностным алгоритмом с полиномиальным временем выполнения, а его ввод имеет полиномиально ограниченный размер.
Многие случайные переменные легко поддаются распознаванию. Рассмотрим пример.
Пример 4.4. Пусть Е = {fc-битовые простые числа} и Е' = {^-битовые составные числа}. По определению Т>(а,Е) = 1 тогда и только тогда, когда Prime_Test(a) —» ДА, и V(a, Е') = 1 тогда и только тогда, когда PrimeTest(a) —» НЕТ (см. алгоритм 4.5). Если а ЕЕ,то Prob[P(a, Е) = 1] = 1 и Prob[P(a, Е') = = 1] = 0. Если аеЕ', то Prob[P(a, Е) = 1] = 2~к и Prob[P(a, Е') = 1] = 1-2~к. Следовательно, Adv(P) > 1 - 2_(fe_1). ?
Определение 4.15 (Полиномиальная неразличимость). Пусть ансамбли Е, Е' и параметр безопасности к удовлетворяют условиям, указанным в определении 4.14. Ансамбли Е и Е' называются полиномиально неразличимыми, если для пары {Е,Е') не существует ни одного классификатора с преимуществом Adv > 0, которое при всех достаточно больших значениях к не было бы пренебрежимо малым.
168
Часть II. Математические основы I
В теории вычислительной сложности приняты следующие вполне правдопо- I добные предположения.
