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


Доказательства от противного



Pdf көрінісі
бет53/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   49   50   51   52   53   54   55   56   ...   249
Криптография Катц

3.3.2 Доказательства от противного 
Если мы хотим доказать, что данная конструкция вычисляемо надежная, тог-
да мы должны опираться на недоказанные допущения3 (в случае если система 
не является информационно-теоретически надежной). Сначала мы предполо-
жим, что некоторая математическая задача является сложной или что некото-
рый криптографический примитив низкого уровня надежен, а затем докажем
___________________________________________________________
² Здесь используется не совсем стандартная терминология, обратите внимание на то, что по-
нятие «поточный шифр» используется разными людьми по-разному (хотя и в связанных между 
собой случаях). Например, некоторые используют его, когда говорят о ttÆ (см. ниже), а некото-
рые используют его, когда говорят о конструкции 3.17 в качестве примера ttÆ .


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. 


77


Достарыңызбен бөлісу:
1   ...   49   50   51   52   53   54   55   56   ...   249




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

    Басты бет