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

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

ОГЛАВЛЕНИЕ

Следующая >>

- - 4671,9

Из последней строки таблицы следует, что прообразом элемента
3 относительно функции
X -ж^ (mod 10 403)
служит число т = 4672.


16.4. Случайная саморедукция
Мы уже отмечали, что недостатки криптографической схемы Мер-
кля-Хеллмана и других криптосистем, основанных на теории слож-
16.4- Случайная саморедукция

ности, возникают ввиду того, что эти схемы ассоциированы с труд­
ными в общем случае, но легкими при средних значениях параме­
тров проблемами. Возникает естественный вопрос: откуда мы зна­
ем, что задача RSA или проблема выбора Диффи-Хеллмана изба­
влены от этого недостатка? Не может ли так оказаться, что при
известных модуле N и шифрующей экспоненте Е уравнение
С = т^ {modN)
трудноразрешимо при некоторых С, но легко решается для средних
значений?
Оказывается, можно доказывать, что задача RSA при фикси­
рованном модуле N и проблема выбора Диффи-Хеллмана с данной
группой А являются трудными в среднем случае.
Техника доказательства основывается на случайной саморедук­
ции, сводящей конкретные начальные условия проблемы к случай­
ному набору исходных данных. Это означает, что возможность ре­
шения задачи в среднем случае обеспечивает нам успех и в самом
наихудшем. Значит, сложность решения задачи реально не зависит
от того, наихудший или средний случай Вы рассматриваете.

Лемма 16.7. Проблема RSA позволяет применить к ней случайную
саморедукцию.
Доказательство. Пусть нам нужно решить уравнение
С = т^ (modN)
относительно т , причем считается, что С здесь относится к «наи­
более сложным» исходным данным. Сведем уравнение к «среднему»
случаю, выбрав произвольным образом 5 G (Z/7VZ)* и положив
С = S^C,
Теперь мы пытаемся решить уравнение
С' = т'^ (modiV)
относительно неизвестной т\ Если нам не повезло, и мы опять при­
шли к трудному случаю, будем выбирать другие значения S до тех
пор, пока не получим «среднего» условия. Предполагая простоту
среднего случая, мы можем решить уравнение С' = т ' (modN)
относительно т ' и вычислить
т^

что даст нам решение поставленной задачи.
408 Глава 16. Теоретическая слодюность

Можно показать, что проблема выбора Диффи-Хеллмана тоже
обладает свойством случайной саморедукции, в том смысле, что
сложность вопроса о том, является ли тройка
{X,Y,Z) = {G\G'>,G%
тройкой Диффи-Хеллмана (т. е. верно ли, что с = а • Ь), не зависит
от выбора значений а, 6 и с. Действительно, рассмотрим тройку:


со случайными f/i, С/2 и У. Если (X, F, Z) — тройка Диффи-Хелл­
мана, то (X', У^, Z') — тоже тройка Диффи-Хеллмана, и наоборот.
Можно показать, что для тройки Диффи-Хеллмана (X, У, Z) ас­
социированные тройки (X', У , Z') равномерно распределены в мно­
жестве всех троек Диффи-Хеллмана. А если начальная тройка не
принадлежала к числу троек Диффи-Хеллмана, то ассоциированные
тройки будут равномерно распределены по множеству всех троек
чисел (а не в множестве троек Диффи-Хеллмана).


16.5. Рандомизированные алгоритмы
Закончим главу обсуждением рандомизированных алгоритмов. Сна­
чала мы сформулируем определения различных типов алгоритмов,
затем соотнесем их с классами сложности и, наконец, приведем не­
сколько примеров.
Напомним, что к проблемам выбора относятся задачи, в которых
спрашивается о выполнении или невыполнении какого-то конкрет­
ного свойства. Приведем определения, в которых названия типов
соответствуют мировым центрам азартных игр.
Алгоритм Монте-Карло,
- Если ответ в проблеме выбора отрицателен, то алгоритм все­
гда выдает ответ «нет».
- Алгоритм выдает положительный ответ с вероятностью боль­
ше или равной ^.
- В остальных случаях алгоритм дает отрицательный ответ, да­
же если истинный ответ в задаче положителен.
Алгоритм Атлантик-Сити.
- Выдает положительный ответ, причем вероятность его пра­
вильности не ниже | .
- Выдает отрицательный ответ с той же вероятностью правиль­
ного ответа.
16.5. Рандомизированные алгоритмы

Алгоритм Лас-Вегас.
- Заканчивает работу и выдает правильный ответ с вероятно­
стью большей или равной ^.
- В остальных случаях алгоритм не заканчивает работу.

В этих определениях мы предполагаем, что алгоритм работает
в течение полиномиального времени относительно размера входных
данных. Очевидно, можно обобщить эти определения и на класс за­
дач, не относяп];ихся к проблеме выбора.
Переключим внимание на классы сложности. Предположим, что
у нас есть запрос / и возможный свидетель г^;, чей размер поли­
номиально зависит от размера запроса / . Нам нужно определить,
принадлежит ли / множеству S.

Определение 16.8. Говорят, что проблема выбора принадлежит
классу TZV., если найдется алгоритм А, который по введенным в него
запросу / и свидетелю w осуш;ествляет следуюш;ее:
- если / G 5, то по крайней мере для половины возможных сви­
детелей алгоритм определит, что I Е S;
- если / ^ 5, то при любом свидетеле алгоритм выдаст ответ:


Поскольку из утверждения «по крайней мере для половины сви­
детелей алгоритм определит, что / G S» непосредственно следует,
что «по крайней мере А^ЛЯ ОДНОГО свидетеля алгоритм определит, что
/ G «S», имеет место включение TZV С AfV. Кроме того, очевидно,
V СПТ.
Класс задач TZV имеет особое значение, т. к. А^ЛЯ каждой задачи
этого класса суп1;ествует вероятностный алгоритм А, определяю-
п];ий, принадлежит ли данный запрос / фиксированному множеству
S при любом множестве S. Мы генерируем к случайных свидете­
лей Wi и прогоняем алгоритм Л(/, Wi) к раз при разных значениях г.
Если этот алгоритм выдал ответ I Е S хотя бы на одном проходе,
можно сделать вывод, что / действительно принадлежит 5. Если же
каждый раз алгоритм будет выдавать сообш;ение / ^ 5, то можно
предположить, что / ^ 5, причем предположение будет ошибочным
только в одном случае из 2^, Связывая это наблюдение с разбиением
алгоритмов на типы, мы видим, что
если проблема выбора принадлеоюит классу TZV, то для нее най­
дется алгоритм Монте-Карло.
410 Глава 16. Теоретическая слодюность

Определим еще один класс задач.

Определение 16.9. Проблему выбора относят к классу BVV^ если
для нее найдется алгоритм Л, который по введенным запросу / и
свидетелю w делает следующее:
- если / G 5, то по крайней мере при | всех возможных свиде­
телей алгоритм определяет, что I Е S;
- если / ^ 5*, то по крайней мере при | всех возможных свиде­
телей алгоритм выдает ответ I ^ S.

Очевидно, имеет место утверждение:
если проблема выбора относится к классу BW, то для нее най­
дется алгоритм Атлантик-Сити,
Наконец, определим класс задач ZW как
ZVr = nVn со- nV.
Тогда
для любой задачи класса ZVV найдется алгоритм Лас-Вегас.
Имеют места следующие включения:
V С ZVV cnV С MV П BVV.
Тест Ферма и тест Миллера -Рабина на простоту служат приме­
рами алгоритма Монте-Карло, тестирующего числа на наличие не­
тривиальных делителей. Напомним, что упомянутые тесты по дан­
ному числу N работают так:
- если N — простое, то всегда выдают ответ Л О Ж Ь (или прав­
доподобно простое);
- если N — составное, то дают ответ ИСТИНА с вероятностью
^ ^, в противном случае следует ответ Л О Ж Ь .
Следовательно,
задача о разлоэюимости числа на мноэюители леэюит в TZV.
Повторяя тест Монте-Карло, мы можем приблизить вероятность
правильного ответа сколь угодно близко к единице.
Алгоритм Адлемана-Хуанга доказательства простоты числа —
пример алгоритма Лас-Вегас тестирования простоты. На вход это­
го алгоритма подается натуральное число N. Если оно составное.
16,5. Рандомизированные алгоритмы

то алгоритм может и не окончиться, но если он все же остановится,
то скажет нам абсолютно верно, простое число N или нет. Значит,
задача о простоте числа принадлеэюит классу ZW.
Появившийся до Адлемана и Хуанга алгоритм доказательства
простоты, основанный на эллиптических кривых, не гарантирует
конечного времени работы при произвольном простом р, но прак­
тически всегда это время конечно.

Краткое содержание главы

- Теория сложности имеет дело с самыми плохими входными
данными алгоритма, решаюп1;его данную проблему выбора.
- Некоторые задачи решаются легко при средних начальных дан­
ных, однако суш;ествуют такие условия, при которых их чрез­
вычайно трудно решить. Не стоит основывать криптосистемы
на такого сорта задачах.
- Криптографические системы, основанные на задаче о рюкза­
ке, стали притчей во языцах ввиду того, что их легко взломать,
опираясь на приведенные базисы решеток.
- Задачи, которые мы кладем в основу криптосистем с откры­
тым ключом, такие как задача RSA или проблема дискретного
логарифмирования, обладают тем свойством, что вычисление
даже одного бита из ответа настолько же сложно, насколько
трудно узнать весь ответ.
- Такие задачи, как RSA и проблема выбора Диффи-Хеллмана,
являются трудными в среднем случае, поскольку опираясь на
случайную саморедукцию можно свести задачу с фиксирован­
ными исходными данными к задаче со случайными начальны­
ми данными.

Дополнительная литература
Хорошее введение в теорию сложности можно найти в главе 2 Бэча
и Шаллита. Обсуждение связей между теорией сложности и таки­
ми криптографическими концепциями как доказательство с нуле­
вым разглашением, представлено книгой Гольдрайха. О криптоси­
стемах, основанных на задаче о рюкзаке, и методах их взлома с
помощью решеток рассказано в обзорной статье Одлыжко.
Е. Bach and S. Shallit. Algorithmic Number Theory, Volume 1: Efficient
Algorithms. MIT Press, 1996.
412 Глава 16. Теоретическая слоэюиостъ

О. Goldreich. Modern Cryptography, Probabilistic Proofs and Pseudo-
randomness. Springer-Verlag, 1999.
A. Odlyzko. The Rise and Fall of Knapsack Cryptosystems. In Cryp-
tology and Computational Number Theory^ Proc. Symposia in Applied
Maths, Volume 42, 1990.

Контрольные вопросы
16.1.1. Дайте определение классов сложности 7^, AfV и со — MV,

16.1.2. Какое распределение весов в задаче о рюкзаке называют про­
грессивно возрастающим?

16.1.3. Как в криптосистеме Меркля-Хеллмана задача о рюкзаке с
прогрессивно возрастающими весами транслируется в труд­
ную задачу о рюкзаке?

16.1.4. Что подразумевают под сильным предикатом относительно
функции и как это понятие связано с семантической стойко­
стью?

16.1.5. Чем отличаются типы алгоритмов Монте-Карло, Атлантик-
Сити и Лас-Вегас?

16.1.6. Выясните, к какому из трех типов алгоритмов: Монте-Карло,
Атлантик-Сити или Лас-Вегас относятся
(а) /9-метод Полларда;
(б) тест на простоту Миллера-Рабина;
(в) алгоритм Шэнкса извлечения квадратного корня в ?р.

Лабораторные работы
16.2.1. Реализуйте схему Меркля-Хеллмана и атаку на нее, основан­
ную на решетках. Исследуйте практическим путем, насколь­
ко успешна эта атака.

Упражнения
16.3.1. Проверьте справедливость следующих равенств для оракулов
в задаче RSA\
Oh{C,N) = Oi{C'2^ {modN),N),
Oi{C,N) = Oh{C-2-^ {modN),N),
16.5. Рандомизированные алгоритмы

16.3.2. [Предполагается владение теорией графов.] Покажите,
что рекурсивный алгоритм, определяющий, можно ли рас­
красить данный средний граф в три краски (см. стр.398), в
течение работы пройдет в среднем не более чем через 197
вершин вне зависимости от общего количества вершин в графе.

16.3.3. Покажите, что в нашем определении класса BVV и алгорит­
ма Атлантик-Сити можно заменить константу | на любую
дробь из интервала (^,1).

16.3.4. Докажите, что предположение о существовании односторон­
них функций влечет неравенство V Ф MV,
ГЛАВА 17
ДОКАЗУЕМАЯ
СТОЙКОСТЬ
СО СЛУЧАЙНЫМ
ОРАКУЛОМ

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

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

ОГЛАВЛЕНИЕ

Следующая >>