Основы современной криптографии

защита от гринмейла

Общие положения - часть 3


В-третьих, необходимо уточнить, какой объем вычислений можно считать «практически неосуществимым». Из сказанного выше следу­ет, что эта величина не может быть просто константой, она должна быть представлена функцией от растущего параметра безопасности. В соответствии с тезисом Эдмондса алгоритм считается эффективным, если время его выполнения ограничено некоторым полиномом от дли­ны входного слова (в нашем случае – от параметра безопасности). В противном случае говорят, что вычисления по данному алгоритму практически неосуществимы. Заметим также, что сами криптографи­ческие системы должны быть эффективными, т. е. все вычисления, пред­писанные той или иной схемой, должны выполняться за полиномиальное время.

В-четвертых, необходимо определить, какую вероятность можно считать пренебрежимо малой. В криптографии принято считать та­ковой любую вероятность, которая для любого полинома р и для всех достаточно больших n не превосходит 1/р(n), где п – параметр безо­пасности.

Итак, при наличии всех указанных выше определений, проблема обо­снования стойкости криптографической системы свелась к доказатель­ству отсутствия полиномиального алгоритма, который решает задачу, стоящую перед противником. Но здесь возникает еще одно и весьма се­рьезное препятствие: современное состояние теории сложности вычи­слений не позволяет доказывать сверхполиномиальные нижние оценки сложности для конкретных задач рассматриваемого класса. Из этого следует, что на данный момент стойкость криптографических систем мо­жет быть установлена лишь с привлечением каких-либо недоказанных предположений. Поэтому основное направление исследований состоит в поиске наиболее слабых достаточных условий (в идеале – необходимых и достаточных) для существования стойких систем каждого из типов.

В основном, рассматриваются предположения двух типов – общие (или теоретико-сложностные) и теоретико-числовые, т. е. предполо­жения о сложности конкретных теоретико-числовых задач. Все эти предполо­жения в литературе обычно называются криптографическими.




- Начало -  - Назад -  - Вперед -