В вопросе упоминается доказательство путем сведения к сложной математической задаче (например, Computational Diffie-Hellman). Это не единственное распространенное использование доказательства путем редукции для доказательства безопасности криптосистемы: вместо сложности математической задачи мы часто предполагаем наличие криптографического строительного блока с некоторым предполагаемым криптографическим свойством, таким как блочный шифр, вычислительно неотличимый от случайной перестановки, когда ключ является случайным, или хэш, который, как предполагается, доступен злоумышленникам только как случайный оракул.
Для некоторых систем у нас есть прямое доказательство совершенной безопасности с помощью теоретико-информационного аргумента, например. установив, что никакая информация об открытом тексте не может быть получена из зашифрованного текста в одноразовом блокноте.Проблема в том, что всем системам, безопасность которых можно доказать с помощью этой линии доказательства, требуется секретный ключ, равный по размеру всему открытому тексту, когда-либо переданному (очевидно, если открытый текст предполагается случайным), и поэтому они непрактичны. В частности, ни один из них не может быть надежным шифром по математическому определению этого. Таким образом, для доказательства практических криптосистем теоретико-информационная линия аргументации должна использоваться в сочетании с доказательством путем редукции и предположения.
Я не знаю другого математического метода доказательства безопасности для криптосистем. Я не знаю практической криптосистемы с полным математическим доказательством безопасности. И даже если мы сэкономим на практичности, существование надежного шифра подразумевало бы P-NP, а нас там нет.
Однако у нас также есть аргументы безопасности. Мы можем спроектировать криптосистему или стандартный блок (такой как блочный шифр или хэш) с параметрами (в частности, числом циклов и шириной переменных), изучить, насколько сложность взлома известными криптоаналитическими методами становится сложнее, когда эти параметры растут, и убедить себя, что эта тенденция будет продолжаться (это самое сложное и самое неопределенное); затем сделайте вывод, что при определенных достаточно больших параметрах мы защищены от этих известных атак.
За редким исключением одноразового блокнота, возможно в сочетании с квантовым распределением ключей, все развернутые криптографические системы, которым разумно доверять, используют эту более позднюю линию аргументации.
