<< Предыдущая

стр. 61
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

ке, можно построить алгоритм решения задачи в классической по­
становке. Соответствующий алгоритм приведен ниже, где оператор
0(W[1] , . . . ,W[n] ,S) обозначает оракула, решающего проблему вы­
бора.

if (0(W[13,..., W[n],S)== False)
{ Output False; }
T=S;
16.1. Классы полиномиальной сложности

Ь[1] = Ь[2] = . . . = Ь[п] = 0.
for ( i = l ; i<=n; i++)
{ i f (T==0)
{ Output ( b [ l ] , . . . . b [ n ] ) . }
i f 0(W[i+l], . . . , W[n],T-W[i])==True)
{ T=T-W[i]; b [ i 3 = l ; }
}
Говорят, что проблема выбора W принадлежит классу задач
сложности Р , если существует алгоритм, отвечающий «да» на любой
запрос / (на который должен последовать положительный ответ) за
полиномиальное время. Мы измеряем время в терминах битовых
операций, и полиномиальность означает, что число битовых опера­
ций ограничено некоторой функцией, полиномиально зависящей от
битового размера запроса / . Если ответ на запрос должен быть от­
рицательным, то от алгоритма вообще не требуется ответа, но если
он все же последует, то должен быть верным.
Заменяя в предыдущем определении положительный ответ на от­
рицательный, мы получим класс задач со — Р . К нему относятся те
проблемы выбора, для которых существует алгоритм, идентифи­
цирующий запросы с подразумеваемым отрицательным ответом за
полиномиальное время.

Лемма 16.3.
р = со - Р.
Доказательство. Пусть А — алгоритм, правильно отвечающий на
запрос / , ответ на который должен быть положительным, за время
п^ для некоторой константы с. Трансформируем его в полиномиаль­
ный алгоритм, дающий верный ответ на запрос с подразумеваемым
отрицательным ответом за время п^ + 1. Для этого мы запустим
алгоритм А и если он не даст ответа на запрос в течении п^ шагов,
то остановим его и дадим ответ «нет». •
К проблемам класса сложности V относятся те, для решения ко­
торых существует эффективный алгоритм. Другими словами, это
задачи, в которых легко проводить вычисления. Например,
- проверка равенства z = х - у для данных целых чисел ж, у и z
принадлежит классу Р , если умножение — легкая операция;
- проверка соответствия данного шифротекста С ключу к и со­
общению т в любимой Вами криптосистеме.
В последнем примере, естественно, предполагается, что алгоритмы
396 Глава 16. Теоретическая сложность

шифрования и расшифровывания в криптосистеме осуш;ествляются
за полиномиальное время. Если же Ваш любимый шифруюп1;ий ал­
горитм требует большего времени, то возникает вопрос, зачем Вы
читаете этот учебник.
Проблему выбора относят к классу MV недетерминированного
полиномиального времени, если для любого запроса с подразуме­
ваемым положительным ответом суш;ествует свидетельство соот­
ветствующего ответа, которое может быть проверено за полиноми­
альное время. Если же ответ на запрос отрицателен, то алгоритм
вообще может не закончиться, но если он все же остановится, то
обязан дать ответ «нет». Свидетельство стоит представлять себе
как доказательство принадлежности запроса / множеству S.
Примеры задач класса MV.
- Является ли данное число N составным? Здесь в качестве сви­
детеля выступает любой нетривиальный делитель числа N.
Проверка осуществляется за полиномиальное время, посколь­
ку операция деления имеет полиномиальную сложность.
- Можно ли раскрасить данный граф к красками? Найти свиде­
теля здесь — это предъявить правильную раскраску.
- Проблема рюкзака при данном наборе весов. Свидетель — пра­
вильная последовательность {bi}.
Обратите внимание на то, что ни в одном из этих примеров не пред­
полагается, что свидетеля можно найти за полиномиальное время.
Единственное требование — проверка должна проводиться за по­
линомиальное число операций. Очевидно, имеет место включение


Основная проблема в области теоретической информатики — это
совпадают ли множества V и AfVl Большинство считает, что спра­
ведлива

Г и п о т е з а 16.4.


Множество со — J\fV определяется аналогично классу со — 'Р как
совокупность задач выбора, имеющих свидетельство отрицательно­
го ответа, которое может быть проверено за полиномиальное время.
В отличие от положения ^\ел с парой со — 7^ и Р , имеет место утвер­
ждение:
Если V ф MV, то MV фсо- MV,
Поэтому стоит считать, что J\fV 7^ со — MV.
16.1. Классы полиномиальной слоэюности 397

Выясним на примере, насколько малым может быть свидетель
для задачи из класса AfV. Рассмотрим задачу о множителях, т.е.
вопрос о наличии нетривиальных делителей у данного числа п G Z.
Как уже было отмечено, эта задача принадлежит классу AfV. Дока­
зать разложимость числа можно следующими способами.
- Предъявить нетривиальный множитель. Здесь размер свиде­
теля равен О (Inn).
- Предъявить свидетеля Миллера-Рабина а. Согласно обобщен­
ной гипотезе Римана справедлива оценка
а ^ 0((1пп)2).
Поэтому размер свидетеля оценивается как O(lnlnn).
Говорят, что данная проблема выбора W является Л/^Р-полной,
если любая задача класса J\fV может быть сведена к ней за полино­
миальное время. Другими словами, это условие означает, что


В некотором смысле, Л/^Р-полные задачи являются самыми трудны­
ми из имеющих решение. Существует огромное число МТ-полвых
задач, из которых нас интересуют всего две:
- задача о раскраске графа,
- задача о рюкзаке.
Нам известно, что задача о делимости натурального числа принад­
лежит классу Л/^'Р, но не известно, является ли она ЛГР-полной. При­
нято считать, что все трудные задачи, на которых основываются
криптографические примитивы, например, факторизация, пробле­
ма дискретного логарифмирования, и т. д., не являются ЛГР-полны­
ми, хотя и лежат в классе J\fV.
Отсюда можно заключить, что задача факторизации не являет­
ся очень сложной проблемой по сравнению с задачами о раскраске
графа или укладке рюкзака. Почему же мы не берем МТ-полпые
проблемы для конструирования криптографических систем? Ведь
они представляют собой класс хорошо изученных трудных задач,
для которых существование эффективного решения крайне сомни­
тельно.
Как мы увидим позже, после знакомства с системой Меркля и
Хеллмана, основанной на задаче о рюкзаке, идея использования J\fV-
полных задач ^1^ля криптографических примитивов плохо реализует­
ся. До этого момента мы лишь упоминали, что теория сложности и,
в частности, ЛГР-полнота имеет дело с наисложнейшим случаем. Для
Глава 16. Теоретическая слооюность

криптографических же целей нам удобны задачи, которые при со­
ответствующем выборе параметров являются трудными в среднем.
Как мы позже убедимся, задача об укладке рюкзака, которую ранее
предлагали использовать в криптографии, всегда имеет «среднюю»
сложность, и при любом выборе параметров можно найти эффек­
тивный алгоритм, который ее решает.
Закончим этот параграф иллюстрацией отличий между труд­
ными и средними задачами на примере задачи о раскраске графа
тремя красками. Хотя в наихудшем случае задача о возможности
раскраски графа тремя красками является Л/^Р-полной, в среднем
случае ее решение не вызывает больших затруднений. Связано это
с тем, что средний граф, вне зависимости от его величины, не уда­
ется раскрасить в три цвета. Мы приведем алгоритм, который для
почти любого графа даст отрицательный ответ о возможности пра­
вильной раскраски за постоянное число операций.
- Произвольно перенумеруем вершины графа: ?;i, . . . , vt-
- Обозначим цвета как 1, 2 и 3.
- Будем обходить граф согласно только что выбранной нумера­
ции вершин.
- Проходя очередную вершину, будем красить ее в наименьший
из возможных цветов (т.е. наименьший элемент из {1,2,3},
который не использован для окрашивания смежной вершины).
- Если дальнейшая раскраска невозможна, то возвраш;аемся к
последней окрашенной вершине и окрашиваем ее в следуюш;ий
доступный цвет.
- Если будут исчерпаны все возможности окраски первой вер­
шины, то алгоритм останавливается и делается вывод: данный
граф невозможно раскрасить тремя красками.
- Если, следуя алгоритму, раскрашены все вершины, то делает­
ся вывод о том, что данный граф можно раскрасить тремя
красками.
Интересно, что среднее число вершин случайного графа, через ко­
торые пройдет алгоритм в процессе работы, не зависит от числа
всех вершин в графе и равно 197.


16.2. Криптосистемы, основанные на задаче о
рюкзаке
в основу одной из наиболее ранних криптосистем с открытым клю­
чом была заложена задача о рюкзаке, которая считалась трудной
16.2. Криптосистемы, основанные на задаче о рюкзаке

при общем выборе начальных данных. Фактически, она принадле­
жит классу ЛfV'Uoляыx задач, однако, можно показать, что крипто­
система, основанная на ней, не является стойкой.
Идея состоит в выборе двух наборов параметров задачи о рюк­
заке: открытый набор делает задачу трудноразрешимой, а секрет­
ный — легкой. Кроме того, должна существовать некоторая допол­
нительная функция-ловушка, с помощью которой трудная задача
трансформируется в легкую.
Такой подход сильно напоминает предположения в криптосисте­
ме RSA: очень трудно извлечь корень степени е из заданного числа
по составному модулю, но задача становится почти тривиальной,
если модуль — простое число. Обладание дополнительной инфор­
мацией, а именно, разложением модуля криптосистемы на простые
делители, позволяет свести сложную задачу к легкой. Однако суще­
ственное различие между задачей RSA и проблемой рюкзака состо­
ит в том, что при подходящем выборе разложение модуля на множи­
тели — задача трудная в среднем, а найти параметры для трудной
в среднем проблемы рюкзака очень сложно, несмотря на то, что
общая задача о рюкзаке труднее общей задачи факторизации.
В то время, как общая задача о рюкзаке очень сложна, существу­
ет большой класс начальных данных, при которых задача об уклад­
ке решается быстро. Эти параметры относятся к так называемым
прогрессивно возрастающим последовательностям. Параметры для
простых задач выбираются так, чтобы каждый из следующих весов
был больше суммы всех предыдущих, т. е.
г-1
Wi ^ ^Щ-


Например, последовательность
{2, 3, 6, 13, 27, 52}
обладает этим свойством. Можно взять и такие веса:
{1,2,4,8,16,32,64,...}.
Если веса в задаче о рюкзаке обладают этим свойством, то выбор
очередного веса, который следует положить в рюкзак — линейная
операция. Продемонстрируем это на алгоритме:

for (i=n; i > = l ; i—)
{ i f (S>=w[i])
{ b[i]=l;
Глава 16. Теоретическая сложность

S=S-w[i];
}
else
{ b[i]=0; }
}
i f (S==0) then
напечатать ( b [ l ] ,b[2] , . . . , b [ n ] )
else
напечатать «нет решения»

Криптосистема Меркля-Хеллмана в качестве секретного ключа
выбирает задачу о рюкзаке с прогрессивно возрастающей последо­
вательностью весов и по ней (используя секретное преобразование)
формулирует «сложную» задачу о рюкзаке — открытый ключ. Сек­
ретное преобразование опирается на скрываемые взаимно простые
натуральные числа пит. Оно заключается в умножении всех ве­
сов прогрессивно возрастающей последовательности на п (modm).
Пусть, например, секретный ключ состоит из последовательности^
{2, 3, 6, 13, 27, 52},
п = 3 1 и т = 105. Соответствующий открытый ключ — «сложная»
задача о рюкзаке с весами
{62, 93, 81, 88, 102, 37}.
Считается, что только знающий числа тип способен трансформи­
ровать «сложную» задачу о рюкзаке в простую.
Чтобы зашифровать сообщение. Боб разбивает открытый текст
на блоки, размер которых совпадает с числом весов в задаче, и скла­
дывает те веса, у которых соответствующие биты в блоке равны 1.
Пусть, например, открытый текст имеет вид:
СООБЩЕНИЕ = 011000 110101 101110.
Первый блок сообщения — 011000 говорит о том, что нужно сло­
жить второй и третий веса. При этом получится 93 + 81 = 174 —
первое число шифротекста. Второй блок, 110101, диктует сложить
веса с номерами 1, 2, 4 и 6: 62 + 93 + 88 + 37 = 280. Наконец, сумма,
соответствующая последнему блоку, равна 62 + 81 Н- 88 + 102 = 333.
Таким образом. Боб получает шифротекст:
174,280,333.
^ Чтобы подчеркнуть секретный характер информации, все секретные цифры
набраны полужирным шрифтом. — Прим. перев.
16,2. КриптосистемЫу основанные на задаче о рюкзаке

Законный пользователь системы осведомлен о секретном ключе п, т
и последовательности {2, 3, 6, 13, 27, 52}. Поэтому, умножая каж­
дый блок шифротекста на п˜^ (modm), он сводит сложную задачу
о рюкзаке к простой. В нашем примере п˜^ = 61 (modm), откуда
174 61 = 9 = 3 + 6 = 011000,
280 61 = 70 = 2 + 3 + 13 + 52 = 110101,
333 61 = 48 = 2 + 6 + 13 + 27 = 101110.
Процесс расшифровывания опирается на простую задачу о рюкза­
ке с весами {2, 3, 6, 13, 27, 52} и приведенный выше алгоритм ее
решения.
Конечно, в нашем простом примере мы использовали всего 6

<< Предыдущая

стр. 61
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>