Научная литература
booksshare.net -> Добавить материал -> Криптография -> Венбо Мао -> "Современная криптография" -> 63

Современная криптография - Венбо Мао

Венбо Мао Современная криптография. Под редакцией Клюшиной Д.А. — М. : Издательский дом Вильямс, 2005. — 768 c.
ISBN 5-8459-0847-7
Скачать (прямая ссылка): sovremennaya_kriptografiya.djvu
Предыдущая << 1 .. 57 58 59 60 61 62 < 63 > 64 65 66 67 68 69 .. 311 >> Следующая

Предположение 4.1 (Предположение об общей неразличимости). Существу- i ют полиномиально неразличимые ансамбли.
Ансамбли ?2_Рпте и ?з_Рпте считаются полиномиально неразличимыми. I Иначе говоря, если некто предъявит нам множество целых чисел, которые все сгенерированы в ходе либо эксперимента Е2prime, либо эксперимента ?з_ргт1еэ а их количество ограничено полиномом, и мы применим наилучший из классификаторов, то мы не сможем их распознать за разумное время.
Поскольку мы можем факторизовать число N и правильно ответить на во- I прос, преимущество классификатора не должно превосходить функцию
ехр ^(1,9229994----1- o(l))(logAT)s(koglogN)i^j . Однако эта величина слишком мала и должна быть проигнорирована. Мы не сможем распознать два ансамбля, потому что преимущество наилучшего классификатора, который мы могли бы применить, имеет ничтожно малое преимущество, зависящее от размера целых чисел, входящих в ансамбли. Преимущество такого классификатора представляет собой медленно растущую функцию (slow-growing function), зависящую от объема вычислительных ресурсов. Здесь термин "медленно растущая" означает, что даже если бы мы обладали огромными вычислительными ресурсами, преимущество увеличилось бы крайне мало, и ситуация осталась бы безнадежной.
Полиномиальная неразличимость представляет собой важный критерий стойкости многих криптографических систем и протоколов. Существует много практических способов создать полиномиально неразличимые ансамбли, полезные для современной криптографии. Например, важным компонентом криптографии является генератор псевдослучайных чисел (pseudo-random number generator). Псевдослучайные числа, порождаемые такими генераторами, имеют полностью детерминированное распределение, зависящее от начального числа (seed). Хороший датчик генерирует псевдослучайные числа, полиномиально неотличимые от I истинно случайных чисел, т.е. распределение псевдослучайных величин, порож- | денных таким генератором, и равномерное распределение строк, имеющих такую I же длину, являются полиномиально неразличимыми. Исходя из этих соображений, можно уточнить предположение 4.1 следующим образом.
Предположение 4.2 (Неразличимость псевдослучайности и истинной случайности). Существуют псевдослучайные функции, которые невозможно отличить от истинно случайных функций за полиномиальное время.
В главе 8 мы рассмотрим псевдослучайную функцию (генератор псевдослу- и чайных чисел), которая является полиномиально неотличимой от равномерного распределения. В главе 14 мы продолжим изучение криптосистемы с от-
Глава 4. Вычислительная сложность
169
крытым ключом, широко известной как криптосистема Голдвассера-Микали (Goldwasser-Micali cryptosystem). Ее стойкость основана на использовании полиномиально неразличимых ансамблей, связанных с экспериментами Е2prime и Е3 prime (см. раздел 6.5.1). В качестве еще одного примера полиномиально неразличимых ансамблей можно назвать кортеж Диффи-Хеллмана (Diffie-Hellman tuple) (определение 13.1 в разделе 13.3.4.3), состоящий из четырех элементов определенной абелевой группы (abelian group), и случайную четверку, состоящую из элементов той же группы. Они обеспечивают стойкость криптосистемы Эль-Гамаля (ElGamal cryprosystem) и многих протоколов с нулевым разглашением (zero-knowledge proof protocol). В дальнейших главах мы неоднократно будем использовать понятие полиномиальной неразличимости.
4.8 Теория вычислительной сложности и современная криптография
В заключение обсудим связь между вычислительной сложностью и современной криптографией.
4.8.1 Необходимое условие
С одной стороны, современная криптография, основанная на теории вычислительной сложности, в качестве необходимого условия использует предположение, что V Ф NV. Назовем это условие гипотезой V Ф MV1.
С другой стороны, алгоритм шифрования должен предоставлять пользователю, обладающему правильными ключами, эффективный алгоритм шифрования и/или дешифровки. Кроме того, он должен представлять собой неразрешимую задачу для тех (перехватчиков или криптоаналитиков), кто попытается восстановить по зашифрованному тексту открытый текст или создать корректный зашифрованный текст без применения правильных ключей. Следовательно, в криптосистеме, основанной на NP-задаче, криптографические ключи играют роль свидетельств или вспомогательных исходных данных (более точное название).
Необходимое условие криптографии, основанной на теории сложности, может вызывать возражение. Это возражение основано на предположении, что существует криптосистема, которая могла быть основана на асимметричной задаче из класса V: шифрование может осуществляться с помощью алгоритма, имеющего сложность порядка О(п), а наилучший алгоритм взлома должен был бы иметь порядок сложности О(п10°). Действительно, даже в самом простом случае, когда п = 10, величина О(п10°) представляет собой число, приблизительно равное
7Недавний опрос показал, что большинство специалистов в области компьютерных наук считают, что V ф MV.
170
Часть II. Математические основы
2332. Такое количество операций выходит за все разумные пределы. Следовательно, если бы такая полиномиальная криптосистема существовала, мы были бы< защищены, даже если бы оказалось, что V — NV. Однако, хотя класс V содержит! 0(пк) задач для любого целого числа к, он не содержит ни одной задачи, обладающей свойством асимметричной сложности. Если вариант любой задачи из класса V, имеющий размер п, можно решить за время пк, то из-за детерминированного характера алгоритма для его решения совершенно не требуется время пк+а для* любого q > 0.
Предыдущая << 1 .. 57 58 59 60 61 62 < 63 > 64 65 66 67 68 69 .. 311 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed