Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Еще одна причина недостаточной стойкости современных криптографических систем, основанных на вычислительной сложности, заключается в особенностям прикладной криптографии. Реальные криптографические системы являются ре-^ зультатом компромиссов, которые будут рассмотрены в остальной части книги.
Позитивный подход к разработке и анализу безопасных криптосистем, получивший широкое признание, заключается в формальном доказательстве их стой-' кости (доказуемая стойкость (provable security)) с помощью методов полиномиальной редукции (определение 4.10): любая эффективная атака на криптосистему! путем эффективного преобразования сводится к решению некоторого варианта! одной из известных NP-задач. Такая редукция называется сведением к против воречию (reduction to contradictory), поскольку считается, что все известные NP-< задачи не имеют эффективного решения. Доказательство, полученное таким способом, создает сильную уверенность в стойкости исследуемой криптосистемы. Эта методология рассматривается в главах 14 и 15.
4.9 Резюме
Вычислительная сложность — наиболее важная часть современной криптографии. По этой причине главу, посвященную теории вычислительной сложности, следует рассматривать как самостоятельный и самодостаточный справочник.
Мы начали с понятия вычислимости по Тьюрингу и рассмотрели класс задач, для решения которых применяется машина Тьюринга. Некоторые задачи из этого класса являются разрешимыми (эффективно разрешимыми за полиномиальное время). Они могут быть как детерминированными (класс V), так и недетерминированными (вероятностные полиномиальные задачи из некоторых подклассов" класса W). Остальные задачи являются трудноразрешимыми (в разделе 18.2.3 будет показано, что класс NV является подклассом класса W). Задачи из класса NV не решаются ни детерминированными, ни вероятностными алгоритмами, хотя их принадлежность классу эффективно верифицируется с помощью вспомо-' гательной информации.
Мы ввели понятия вычислительной сложности и описали их приложения в со-' временной криптографии. К ним относятся эффективные алгоритмы (некоторые важные алгоритмы имеют точные оценки временной сложности), О-символи-' ка, полиномиальная редукция, пренебрежимо малые величины, нижние, верхние1 и неполиномиальные оценки, а также неразличимость. Эти понятия будут часто использоваться в остальной части книги.
Глава 4. Вычислительная сложность
173
В заключительной части главы рассмотрена фундаментальная роль, которую играют NP-задачи в современной криптографии.
Упражнения
4.1. Постройте машину Тьюринга для распознавания четных целых чисел. Затем постройте машину для распознавания целых чисел, кратных 6. Подсказка: вторая машина может использовать таблицу операций, сопряженную с первой таблицей и таблицей операций машины Div3, изображенной на рис. 4.2.
4.2. Почему при оценке вычислительной сложности алгоритма более предпочтительной является побитовая сложность, основанная на подсчете битовых операций, а не сложность, основанная на подсчетах количества операций умножения целых чисел?
Подсказка: рассмотрите задачу, варианты которой имеют разные размеры.
4.3. По теореме 4.1 для вычисления gcd(x,y), где х > у, необходимо выполнить log а; операций деления по модулю. Учитывая, что побитовая сложность операции деления по модулю имеет порядок Ofi((loga;)2), для вычисления gcd(a;, у) необходимо выполнить Os((loga;)3) поразрядных операций. Однако, как правило, в учебниках указывается, что затраты на вычисление gcd(x,y) имеют порядок Oe((logx)2). В чем заключается ошибка? Подсказка: обратите внимание на неравенство (4.3.12).
4.4. Докажите утверждения 2 и 3 в теореме 4.2.
4.5. Докажите, что классы РР (Монте-Карло) и РР (Лас-Вегас) являются взаимно дополняющими друг друга (т.е. РР (Монте-Карло) = соРР (Лас-Вегас)). Иначе говоря, докажите, что алгоритм Монте-Карло для распознавания предложения I Е L является алгоритмом Лас-Вегаса для распознавания I Е L, и наоборот. Используя тот же прием, докажите, что ВРР = соВРР.
4.6. В литературе, посвященной теории вычислительной сложности, часто можно прочитать утверждение, что в определении класса ВРР в неравенстве (4.4.1) е — |, а в неравенстве (4.4.2) ^ = |.В нашей книге дано более широкое определение: ее [5 + а, 1), 8 Е (0, | — 0\, где а > О и /3 > 0. Насколько существенной является эта разница?
4.7. Покажите, что в выражении (4.4.5) е(к) —> 1 при к —> со. Подсказка: докажите, что 1 — е(к) —»0.
4.8. Объясните, почему вероятности ошибок в классе ВРР не должны равняться ^, т.е. числа а и /3 в выражении (4.4.11) не должны равняться нулю.
174
Часть II. Математические основы
Подсказка: рассмотрите "несимметричную" монету, у которой вероятность выпадения одной стороны на ничтожно малую величину превышает вероятность выпадения другой. Можно ли определить наиболее вероятный исход, подбрасывая монету и применяя критерий "голосования большинством"?
4.9. Оценивая непротиворечивость протокола QKD, мы указали, что Ева может применять две стратегии: посылать Бобу совершенно новые состояния т фотонов или пересылать ему перехваченные состояния без изменения. Мы оценили непротиворечивость протокола, только если Ева придерживается второй стратегии. Оцените непротиворечивость протокола, если Ева применяет первую стратегию.
