Есть ли преимущество у блочного шифра, который не является эффективно обратимым?

Классическое определение PRP включает эффективную обратимость.

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

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

Я бы сказал, что для многих криптографов аргумент идет еще дальше. Учитывая, что режимы потоковой передачи блочного шифра предпочтительнее для массового шифрования, нужна ли вообще обратимость? Если следовать этой линейной аргументации, можно понять, почему наблюдается возрождение популярности потоковых шифров, и ChaCha20 является очевидным примером. Хотя ChaCha20 производит 512-битный вывод из 512-битного состояния и обновляет состояние с помощью простого счетчика (во многом похожего на режимы CTR и GCM), этот процесс (мы полагаем) необратим. Верно также и то, что ChaCha20 — очень эффективная конструкция (при условии, что аппаратное обеспечение поддерживает эффективное добавление 32-битных слов).

Обратите внимание, что для многих реализаций AES функция раунда расшифровки менее эффективна, чем функция раунда шифрования, поскольку инвертирует MixCol процесс более связан с вычислениями.

PRP - это Псевдослучайная перестановка и мы хотим, чтобы они были неотличимы от случайных перестановок. AES и все блочные шифры должны быть PRP. Перестановка означает, что есть инверсия, и они предназначены для того, чтобы иметь ее и действительно иметь эффективную.

Нам нужен режим работы для блочных шифров, и мы покинули CBC из-за множества атак, которые произошли, несмотря на то, что он защищен Ind-CPA.В настоящее время все шифры TLS 1.3 внутренне используют безопасный режим CTR Ind-CPA (наборы шифров TLS 1.3 — это нечто большее, все они представляют собой режимы шифрования с проверкой подлинности и данными с проверкой подлинности).

Даст ли нам что-нибудь такое расслабление?

Это дает нам много возможностей. Нам не нужно ограничиваться PRP в режиме CTR - он уже был разработан для Псевдослучайные функции (ПРФ); Режим CTR не нуждается в обратной функции. С PRF мы можем использовать широкий спектр функций, которым не нужны обратные функции (есть $2^n!$ PRP и $(2^n)^{2^n}$ PRF для n-битных блочных шифров. Даже мы можем взять хеш-функцию и преобразовать ее в шифрование CTR, как в Сальса. Мы также можем разработать ключевой график практически без затрат.

Использование PRP в режиме CTR может привести к распознаватель длинных сообщений и мы можем устранить это, используя PRF. Если мы используем PRP в режиме CTR, нам нужно ограничить количество блоков шифрования из-за леммы о переключении PRP-PRF.

Режим CTR также не требует заполнения, поэтому они невосприимчивы к атакам оракула заполнения.

ChaCha20 и Salsa20 являются хорошо известными примерами, которые имеют нулевую стоимость расписания ключей, дизайн ARX с дружественным процессором. Они имеют встроенный режим CTR и очень быстры в программном обеспечении.

Действительно, PRF лучше подходит для различных режимов, таких как CTR, чем PRP.Проблема в том, что мы не знаем, как построить хорошие PRF, кроме как из PRP.

1. Один из способов состоит в том, чтобы просто представить, что наша PRP является PRF: и это верно, пока не выдается определенное количество данных (граница дня рождения, см. лемму о переключении PRP/PRF).

2. Другим часто используемым способом является вычисление PRP/перестановки и добавление ввода к выводу. Это не улучшает привязку ко дню рождения, но этот трюк делает функцию необратимой, что имеет решающее значение в некоторых случаях (например, в ChaCha, упомянутом @Daniel S). Он также используется в хеш-функциях в стиле Меркла-Дамгарда для построения функции сжатия (Дэвиса-Мейера).

3. Добавление/объединение двух перестановок является хорошим PRF, но это дорого.

4. Достаточное усечение вывода также является хорошим PRF, но опять же дорого.

Стоит упомянуть криптографию на основе губки, основанную на общедоступных перестановках, которые оцениваются только в прямом направлении. Другими словами, не требуется, чтобы перестановка была очень эффективно обратимой.