Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
579
Свойство 15.1. Свойства доказательства, основанного на "сведении к противоречию".
1. Редукция должна быть эффективной. В идеале удачливый взломщик, успешно организующий атаку, должен решить трудноразрешимую задачу, лежащую в основе криптографической схемы.
2. Условия неразрешимости, обеспечивающие стойкость криптографической схемы, должны быть как можно более слабыми. В идеале для стойкости схемы шифрования с открытым ключом, основанной на применении однонаправленной функции с секретом (OWTF), единственным условием должна быть невозможность инвертировать эту функцию (помните, что функции OWTF являются частным случаем схемы OWTP).
Свойство 15.1.1 имеет практическое значение: неэффективная редукция, даже за полиномиальное время, может уничтожить связь между атакой и решением трудноразрешимой задачи. Например, если редукция связана с полиномом степени 8, а параметр безопасности равен 1024, то временная сложность редукции имеет порядок 10248 = 280. Если предположить, что существует успешная атака, взламывающая систему за Ю-6 с, то на применение атакующего алгоритма для решения трудноразрешимой задачи понадобится 38 миллиардов лет! Такое доказательство стойкости не только бессмысленно, но и противоречит определению математического доказательства: известные методы решения трудноразрешимых задач могут оказаться намного эффективнее, чем редукция! Фактически, как показано в разделе 15.2.5, даже если сложность редукции ограничена полиномом второй степени, при стандартном размере параметра безопасности доказательство становится некорректным.
Может показаться, что желательное свойство 15.1.2 имеет меньшее практическое значение, поскольку оно выглядит слишком общим: если слабые предположения не ограничивают ход доказательства, то доказательство следует строить исключительно на них. Поскольку доказательство стойкости является довольно важной частью исследования, свойство 15.1.2 имеет большое практическое значение. Его важность особенно ярко проявляется при разработке криптографических систем: более слабые предположения легче удовлетворить, используя практичные и доступные криптографические конструкции. Следовательно, криптографические системы, основанные на слабых предположениях, имеют более высокий уровень стойкости, чем криптосистемы, основанные на более сильных предположениях.
Как показано выше, доказательство стойкости схемы RSA-OAEP, основанное на модели случайного оракула, не полностью удовлетворяет свойству 15.1.1, поскольку редукция становится некорректной уже при стандартном размере модуля RSA. Более того, это доказательство недостаточно удовлетворяет и свойству 15.1.2, поскольку кроме условия, касающегося функции RSA (предположе-
580
Часть V. Методы формального доказательства стойкости
ние 8.3), для него необходимо выполнение намного более строгого ограничения: функция хэширования, применяемая в схеме ОАЕР, должна обладать свойствами случайного оракула. Это чрезмерно сильное предположение: как показано в разделе 10.3.1.2, в природе не существует случайного оракула. Следовательно, это предположение неразумно. Действительно, с точки зрения практики из доказательства стойкости схемы RSA-OAEP следует, что при конструировании этой схемы мы должны применять функцию хэширования очень высокого качества. К сожалению, это условие не гарантирует нам уверенности, которую дает математическое доказательство стойкости.
Формальное доказательство стойкости криптосистемы с открытым ключом, основанное исключительно на неразрешимости задачи OWTP, называется доказательством, основанным на стандартных предположениях о неразрешимости (standard intractability assumption(s)). Такое доказательство устанавливает реальную стойкость криптосистемы: оно гарантирует, что криптосистему невозможно взломать, не нарушив предположений о неразрешимости задачи, лежащей в ее основе.
Существует большое количество доказуемо стойких к атаке IND-CCA2 криптосистем, основанных на стандартных предположениях о неразрешимости. Примером такой системы является схема Долева [100], стойкая к атаке NM-CCA2 (эквивалент атаки IND-CCA2). Однако, как показано в разделе 14.5.3, необходимость применять в схеме Долева доказательство NIZK делает эту криптосистему непригодной для практического применения.
Криптосистема с открытым ключом Крамера-Шоупа [84] является первой криптосистемой с открытым ключом, обладающей практической эффективностью и доказанной стойкостью к атаке IND-CCA2 при стандартных предположениях о неразрешимости. В дальнейшем будет показано, что эта схема имеет строгое доказательство стойкости, основанное на "сведении к противоречию", которое называется линейной редукцией (linear reduction). Итак, схема шифрования с открытым ключом Шоупа-Крамера идеально удовлетворяет условиям 15.1.
15.3.2 Схема Крамера-Шоупа
Схема шифрования с открытым ключом Крамера-Шоупа представляет собой вариант семантически стойкой схемы шифрования Эль-Гамаля (см. раздел 14.3.5), устойчивый к атаке ССА2. Как и в семантически стойкой схеме шифрования Эль-Гамаля, стандартное предположение о неразрешимости, гарантирующее стойкость схемы Крамера-Шоупа, относится к задаче принятия решений Диффи-Хеллмана (задаче DDH).
