Введение в современную криптографию
Доказательства от противного
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| 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. |