76
что данная конструкция, опирающаяся на эту задачу и (или) этот примитив, надежна
при этом допущении. В разделе 1.4.2 мы уже очень подробно объяснили, почему та-
кой подход предпочтителен, поэтому мы больше не будем повторять свои аргументы.
Доказательство того, что криптографическая
конструкция надежна,
пока не-
которая задача трудна для решения, обычно сопровождается явно выраженным
доказательством от противного, показывающим, как преобразовать любого эф-
фективного противника A, который успешно «взломает» систему, в
эффективный
алгоритм Ar, который решит задачу, считающуюся сложной для решения. По-
скольку это
так важно, мы пройдемся по общей схеме такого доказательства более
детально. (Мы рассмотрим множество конкретных примеров в книге, начиная с до-
казательства теоремы 3.18.) Начнем с предположения о том, что некоторая задача X
не может быть решена (в некотором точно определенном смысле) с помощью поли-
номиально-временного алгоритма за исключением пренебрежимо малой вероятно-
сти. Мы хотим доказать, что некоторая криптографическая конструкция П является
надежной (опять-таки, в некотором точно определенном смысле). Доказательство
осуществляется по следующим этапам (см. также Рисунок 3.1):
3.3.2.1 Зафиксируем некоторого эффективного (т.е.
вероятностного полино-
миально-временного) противника A, атакующего П.
Определим, что вероят-
ность успеха этого противника составляет ε(n).
3.3.2.2 Сконструируем эффективный алгоритм Ar, называемый «редукция»,
который пытается решить задачу X, используя противника A в качестве подпро-
граммы. Здесь важный момент заключается в том, что Ar ничего не знает о то,
как работает A. Единственное, что известно Ar: предполагается, что A атакует
Π. Итак, задан некоторый вводный образец x задачи X, наш алгоритм Ar будет
моделировать для A такой образец Π, что:
3.3.2.2.1 Поскольку A может сказать, что взаимодействует с Π. То есть вид A
при запуске в качестве подпрограммы Ar должен быть распределен идентично
(или хотя бы близко) виду A при взаимодействии с Π напрямую.
3.3.2.2.2 Если A успешно «взламывает» образец Π, симулированный с помо-
щью Ar, это должно позволить Ar решить заданный ему образец x, хотя бы с
обратной полиномиальной вероятностью 1/p(n).
3.3.2.3 Взятые в совокупности 2(a) и 2(b) подразумевают, что Ar решает X с
вероятностью ε(n)/p(n). Если ε(n) не пренебрежимо мала, тогда таковой не яв-
ляется ε(n)/p(n). Кроме того, если A эффективен, тогда мы получаем эффектив-
ный алгоритм Ar, решающий X с не пренебрежимо малой вероятностью, что
противоречит первоначальному допущению.
____________________________________________________________
³В
частности, основным требованием криптографии является недоказанное допущение P ƒ= N P.