QUAD (шифр) - QUAD (cipher)

QUAD
генеральный
Дизайнеров Ком Бербен, Анри Жильбер и Жак Патарен
Впервые опубликовано 28 мая 2006 г. (в Eurocrypt)
Детали шифра
Ключевые размеры 80 бит
Структура многомерная система квадратных уравнений

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

Описание

QUAD опирается на итерацию случайно выбранной многомерной квадратичной системы S = (Q 1 , ..., Q m ) m = kn уравнений от n неизвестных над конечным полем GF (q). Процесс генерации ключевого потока просто состоит в повторении трех следующих шагов для получения (k -1) n значений ключевого потока GF (q) на каждой итерации.

  • Вычислить набор узлов GF (q) значений S (x) = (Q 1 (x), ..., Q kn (x)), где x - текущее значение внутреннего состояния;
  • Выведите последовательность (Q n + 1 (x), ..., Q kn (x)) из (k-1) n значений ключевого потока GF (q).
  • Обновите внутреннее состояние x последовательностью n GF (q) первых сгенерированных значений (Q 1 (x), ..., Q n (x))

QUAD - это современный потоковый шифр, то есть он использует ключ и значение инициализации (IV) для создания последовательности ключевого потока. Также определены параметры Key и IV, которые также основаны на многомерной квадратичной системе.

Безопасность

Безопасность генерации ключевого потока QUAD доказуемо сводится к предполагаемой неразрешимости проблемы MQ, а именно к решению многомерной системы квадратных уравнений. Первое доказательство было проведено над полем GF (2) для старомодного потокового шифра (где ключ - это начальное состояние). Позже он был расширен Бербеном и Гилбертом, чтобы учесть процедуру настройки современного шифра (с этапом настройки, выводящим начальное состояние из ключа). Безопасность всего шифра как псевдослучайной функции может быть связана с предполагаемой неразрешимостью проблемы MQ. Также авторы изучили устойчивость шифра к классическим атакам.

Рекомендуемые параметры

Авторы рекомендуют использовать версию QUAD с 80-битным ключом, 80-битным IV и внутренним состоянием n = 160 бит. Он выводит 160 битов ключевого потока (m = 320) на каждой итерации, пока не будет создано 2 40 битов ключевого потока.

На Eurocrypt 2006 отчеты о скорости были представлены для экземпляров QUAD с 160-битным состоянием и блоком вывода по полям GF (2), GF (16) и GF (256). Эти отчеты о скорости были частью анализа «Эффективных реализаций многомерных квадратичных систем», который был опубликован Бербеном, Биллетом и Гилбертом на SAC 2006. Этот анализ (который также охватывает несколько многомерных схем с открытым ключом, а также поточный шифр QUAD ) частично изучили влияние изменения размера поля на производительность без учета аспекта безопасности.

Обсуждение параметров

Начальная теорема безопасности для QUAD действительна только для поля GF (2), а рекомендуемые параметры не достигают противоречия с доказательством безопасности. Авторы QUAD, которые дали теорему безопасности, признали, что нарушение QUAD при их предложенных параметрах не противоречит теоремам о доказательстве безопасности, когда они предложили схему на Eurocrypt 2006. Однако казалось, что авторы считали их достаточными для обеспечить желаемый уровень безопасности около 2 80 .

Ян, Чен, Бернштейн и Чен изучали безопасность различных наборов параметров в документе «Анализ квадрата» и обнаружили, что некоторые из них очень небезопасны. В их статье обсуждаются как теоретические, так и практические аспекты атаки на QUAD и решения основной сложной проблемы. Например, в этой статье показано, как с помощью XL-Wiedemann разбить экземпляр GF (256) QUAD (256, 20, 20) примерно за 2 66 циклов Opteron и решить основную сложную проблему примерно за 2 45 циклов, что было выполнено успешно. Однако, согласно данной статье, то потребуется около 2 110 , чтобы решить экземпляр (2,160,160) версий QUAD рекомендованных авторов QUAD с использованием XL-Wiedemann.

Исследование Yang et al. подчеркнули тот факт, что теоремы безопасности часто полагаются на сокращения с коэффициентом слабости, и когда это принимается во внимание, ни один из наборов параметров предлагаемых версий не является достаточным для доказательства безопасности. Экземпляр, который будет доказуемо защищенным, будет иметь QUAD (2 320 320), то есть в два раза шире, чем предлагалось изначально.

Теорема безопасности также может быть доказана для GF (q), хотя и с большим коэффициентом неплотности; это и расширения QUAD для более эффективных реализаций предложены Liu et al. (см. ссылку «Безопасные PRNG из специализированных полиномиальных отображений над любым F q »).

Рекомендации