В криптографии доказательства безопасности в основном используют метод доказательства сокращения. Теперь я прочитал много доказательств редукций, а также сделал некоторые из них самостоятельно, и я думаю, что понимаю это довольно хорошо. Читая эти корректуры, я заметил два основных стиля такой редукции.
Скажем, у нас есть схема $В$ на основе $А$. Мы знаем $А$ безопасно. Если кто-то хочет доказать безопасность $В$ сводя его к безопасности $А$ он может действовать следующим образом:
- Стиль: Предположим, что противник может сломаться. $В$ $\Rightarrow$ Для сокращения можно построить нового противника, ломающего $А$ используя взлом противника $В$ $\Rightarrow$ Результатом является противоречие, которое показывает, что нет серьезного противника против $В$
- Стиль: Предположим, против произвольного ppt противника $В$ $\Rightarrow$ Показать (например, с помощью стохастического анализа эксперимента), что нарушение $В$ так же сложно, как сломать $А$, поэтому уменьшите сложность взлома $В$ по сложности взлома $А$ $\Rightarrow$ Потому что есть только незначительные противники против $А$ нет несущественного противника против $В$
Конечно, это упрощенно, но я хотел дать вам представление о том, что я заметил.
Мои вопросы: Эти стили действительно существуют? Могут ли они оба (правильно формально записанные) доказать одно и то же? Являются ли они оба (особенно стиль 1.) полными? Для каких доказательств следует использовать какой стиль?
Редактировать: Более точное определение стиля 2.: Во «Введении в современную криптографию» докажите криптосистему на PRG: в стохастическом анализе утверждается, что взлом криптосистемы так же вероятен, как и взлом PRG.Они используют это, чтобы подразумевать, что любой произвольный противник должен быть пренебрежимо мал по моде: поскольку это пренебрежимо мало, а вероятность у них одинаковая, то и другое должно быть пренебрежимо мало.
(Примечание. Вкратце я бы описал 1. как: $B \rightarrow A \rightarrow \unicode{x21af} \rightarrow B$ и 2. как: $B \rightarrow A \rightarrow (B = A) \rightarrow B$)
