Каковы снижения безопасности алгоритмов с симметричным ключом?

Я читал страницу Википедии о постквантовой криптографии. В нем говорится, что желательно, чтобы криптографические алгоритмы сводились к какой-то конкретной математической задаче, то есть неразрешимость системы должна быть по существу проистекающей из сложности какой-либо математической задачи.

Например, криптография на основе решеток, Диффи-Хеллмана, RSA, система МакЭлиса, многомерная криптография сводятся к задаче кратчайших векторов, задаче дискретного логарифмирования, целочисленной факторизации, задаче декодирования синдрома, задаче решения многомерного квадратного уравнения соответственно.

Мне не удалось увидеть примеры алгоритмов с симметричным ключом. Почему это? Я предполагаю, что им не нужно это свойство из-за самой природы криптографии с симметричным ключом?

Это потому, что, поскольку это не криптография с открытым ключом, асимметрия не требуется, и, следовательно, нет необходимости в какой-то системе, которую легко зашифровать, но сложно расшифровать, которая преобразуется в какую-то одностороннюю функцию, которую трудно инвертировать из-за стоящая за ней математика?

спасибо за ответы, было полезно.

мне не удалось увидеть какие-либо примеры алгоритмов с симметричным ключом. но почему?

Есть несколько возможных способов ответить на этот вопрос; наиболее прямолинейным является то, что алгоритмы с симметричным ключом находятся на основе конкретных математических задач (просто мы обычно так не выражаемся).

Вот несколько примеров асимметричных алгоритмов:

например... diffie-hellman, rsa... свести к... задаче дискретного логарифмирования, целочисленной факторизации... соответственно.

Это неправильно; если вам дан Oracle, который может сломать алгоритм Диффи-Хеллмана, нет никакого известного способа использовать его для решения проблем с дискретным журналом; если вам дали Oracle, который может сломать RSA, нет никакого известного способа использовать это для фактора.

Вместо этого то, к чему сводится Диффи-Хеллман, известно как «проблема Диффи-Хеллмана» (технически это либо cDH, либо dDH, в зависимости от того, что делает ваш Oracle); то, к чему сводится RSA, известно как «проблема RSA».

Теперь, в чем разница между «проблемой Диффи-Хеллмана» или «проблемой RSA» и «проблемой AES»? Помимо того факта, что «проблема AES» требует больше времени для описания и кажется более произвольной, я не вижу ее (и, конечно, «проблема AES» достаточно хорошо изучена). И, если мы используем AES в каком-то режиме, обычно есть доказательство того, что безопасность режима сводится к «проблеме AES», следовательно, это не просто глупая игра слов.

Другой способ подойти к вопросу (если мы настаиваем на «простых математических задачах» как способе дисквалификации «проблемы AES») состоит в том, чтобы отметить, что нам известны симметричные примитивы, которые сводятся к просто математическим задачам; однако эти примитивы, как правило, работают намного медленнее (и обычно имеют гораздо большие зашифрованные тексты), чем те, которые мы используем на практике, и поэтому мы никогда их не используем, тем более что мы не знаем никаких доказательств того, что «простая математическая задача» на самом деле сложнее. чем «сложная математическая задача», которую мы используем на практике.

Можно перевернуть это и спросить: «Почему мы настаиваем на том, чтобы основывать асимметричные алгоритмы на конкретных сложных задачах?». Один из ответов заключается в том, что асимметричные алгоритмы пытаются сделать больше, чем симметричный алгоритм; мало того, что асимметричный алгоритм должен выглядеть «случайным», он также должен быть безопасным, даже если злоумышленнику будет дана подсказка в виде открытого ключа. Этот открытый ключ должен быть каким-то образом связан с закрытым ключом, но не очевидным образом (и, конечно, операции, которые легко выполнять при наличии закрытого ключа, должны быть невыполнимы при наличии только открытого ключа). Единственный известный нам способ иметь такие неясные отношения состоит в том, чтобы свести их к более простой сложной проблеме.

Поскольку в симметричной криптографии есть снижение безопасности, они, как правило, применяются к конструкциям, использующим идеализированные примитивы, такие как псевдослучайная функция или псевдослучайная перестановка. Так, например, Луби и Ракофф доказали, что можно построить псевдослучайную перестановку из псевдослучайной функции, используя трехэтапную конструкцию Фейстеля. Точно так же симметричные криптографы могут попытаться доказать, что режим работы блочного шифра расширяет псевдослучайную перестановку размера блока до псевдослучайной перестановки большего фрагмента данных.

Тогда уверенность приходит из веры в то, что используемые нами симметричные примитивы отличимы от их идеализированных псевдослучайных аналогов. Будет ли больше уверенности в утверждении «взломать эту конструкцию так же сложно, как отличить SHA256 от псевдослучайной функции» или «взломать эту конструкцию так же сложно, как решить проблему Диффи-Хеллмана в этой группе», зависит от потребителя.