СВИФФТ

СВИФФТ

Общий
Дизайнеры	Вадим Любашевский, Даниэле Мичиансио, Крис Пейкерт, Алон Розен
Впервые опубликовано	2008
Связано с	Алгоритмы на основе БПФ

В криптографии . SWIFFT собой набор доказуемо безопасных хеш-функций представляет Он основан на концепции быстрого преобразования Фурье (БПФ). SWIFFT — не первая хэш-функция, основанная на БПФ, но она выделяется тем, что предоставляет математическое доказательство своей безопасности. Он также использует алгоритм сокращения базиса LLL . Можно показать, что поиск коллизий в SWIFFT по крайней мере так же сложен, как и поиск коротких векторов в циклических/ идеальных решетках в худшем случае . Предоставляя снижение безопасности для наихудшего сценария сложной математической задачи, SWIFFT дает гораздо более надежную гарантию безопасности, чем большинство других криптографических хеш-функций .

В отличие от многих других доказуемо безопасных хеш-функций, этот алгоритм довольно быстр, обеспечивая пропускную способность 40 Мбит/с на процессоре Intel Pentium 4 с тактовой частотой 3,2 ГГц. Хотя SWIFFT удовлетворяет многим желаемым криптографическим и статистическим свойствам, он не был разработан как «универсальный». цель» криптографическая хэш-функция. Например, это не псевдослучайная функция и не будет подходящим экземпляром случайного оракула . Алгоритм менее эффективен, чем большинство традиционных хеш-функций, которые не доказывают свою устойчивость к коллизиям. Следовательно, его практическое использование будет в основном в приложениях, где доказательство устойчивости к коллизиям особенно ценно, например, в цифровых подписях, которые должны оставаться надежными в течение длительного времени.

Модификация SWIFFT под названием SWIFFTX была предложена в качестве кандидата на функцию SHA-3 на конкурсе хеш-функций NIST. и был отклонен в первом туре.

Алгоритм

Алгоритм следующий:

1. Пусть полиномиальная переменная называется $\alpha$
2. Ввод : сообщение $M$ длины $mn$
3. Конвертировать $M$ в коллекцию $m$ полиномы $p_{i}$ в некотором кольце полиномов $R$ с двоичными коэффициентами.
4. Вычислите коэффициенты Фурье каждого $p_{i}$ с помощью СВИФФТ.
5. Определим коэффициенты Фурье $a_{i}$, так что они фиксированы и зависят от семейства SWIFFT.
6. Поточечное умножение коэффициентов Фурье $p_{i}$ с коэффициентами Фурье $a_{i}$ для каждого $i$.
7. Используйте обратное БПФ для получения $m$ полиномы $f_{i}$ степени $<2n$.
8. Вычислить $f=\sum _{i=1}^{m}(f_{i})$ модуль $p$ и $\alpha ^{n}+1$.
9. Конвертировать $f$ к $n\log(p)$ бит и выведите его.

• Операцию БПФ на шаге 4 легко инвертировать, и она выполняется для достижения диффузии , то есть смешивания входных битов.
• Линейная комбинация на шаге 6 приводит к путанице , поскольку сжимает входные данные.
• Это всего лишь высокоуровневое описание того, что делает алгоритм. Некоторые более сложные оптимизации используются для того, чтобы в конечном итоге получить высокопроизводительный алгоритм.

Пример

Мы выбираем конкретные значения параметров n , m и p следующим образом: n = 64, m = 16, p = 257. Для этих параметров любая фиксированная функция сжатия в семействе принимает двоичный вход длиной mn = 1024 бит ( 128 байт), на выход в диапазоне $\mathbb {Z} _{p}^{n}$, который имеет размер $p^{n}=257^{64}$. Выход в $\mathbb {Z} _{p}^{n}$ можно легко представить с помощью 528 бит (66 байт).

Алгебраическое описание

Функции SWIFFT можно описать как простое алгебраическое выражение над некоторым кольцом полиномов. $R$. Семейство этих функций зависит от трех основных параметров: пусть $n$ будет степенью 2, пусть $m>0$ — небольшое целое число, и пусть $p>0$ быть модулем (не обязательно простым , но удобно выбрать его простым). Определять $R$ быть кольцом $R=\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$, т. е. кольцо полиномов от $\alpha$ имеющие целые коэффициенты по модулю $p$ и $\alpha ^{n}+1$. Элемент $R$ можно записать в виде многочлена степени $<n$ имеющие коэффициенты в $\mathbb {Z} _{p}$. Определенная функция в семействе SWIFFT определяется $m$ фиксированные элементы $a_{1},\ldots ,a_{m}\in R$ кольца $R$, которые называются множителями. Функция соответствует следующему уравнению над кольцом R :

$\sum _{i=1}^{m}(a_{i}\cdot x_{i})$

The $x_{1},\ldots ,x_{m}\in R$ являются полиномами с двоичными коэффициентами и соответствуют двоичному входу длины $mn$.

Вычисление полиномиального произведения

Основная проблема при вычислении приведенного выше выражения состоит в вычислении полиномиальных произведений $a_{i}\cdot x_{i}$. Быстрый способ вычисления этих произведений дает теорема о свертке . Это говорит о том, что при определенных ограничениях справедливо следующее:

${\mathcal {F}}\{f*g\}={\mathcal {F}}\{f\}\cdot {\mathcal {F}}\{g\}$

Здесь ${\mathcal {F}}$ обозначает преобразование Фурье и $\cdot$ обозначает поточечное произведение. В общем случае теоремы о свертке $*$ означает не умножение, а свертку . Однако можно показать, что полиномиальное умножение является сверткой.

Быстрое

Для нахождения преобразования Фурье мы будем использовать БПФ ( быстрое преобразование Фурье ), которое находит преобразование в $O(n\log(n))$время. Алгоритм умножения теперь выглядит следующим образом:Мы используем БПФ для вычисления (всех сразу) коэффициентов Фурье каждого многочлена. Затем мы поточечно умножаем соответствующие коэффициенты Фурье двух полиномов и, наконец, используем обратное БПФ, чтобы получить полином степени $<2n$.

Теоретико-числовое преобразование

Вместо обычного преобразования Фурье SWIFFT использует теоретико-числовое преобразование . Теоретико-числовое преобразование использует корни из единицы в $\mathbb {Z} _{p}$ вместо сложных корней единства. Чтобы это работало, нам нужно убедиться, что $\mathbb {Z} _{p}$ — конечное поле , и эта примитивная 2 n ^й В этой области существуют корни единства. Это можно сделать, взяв $p$ простое такое, что $2n$ делит $p-1$.

Выбор параметра

На параметры m , p , n распространяются следующие ограничения:

• n должно быть степенью 2
• p должно быть простым
• p -1 должно быть кратно 2 n
• $\log(p)$ должно быть меньше m (иначе выходное значение не будет меньше входного)

Возможный выбор: n =64, m =16, p =257. Получаем пропускную способность около 40 Мбит/с, безопасность около $2^{106}$ операции по поиску коллизий и размер дайджеста 512 бит.

Статистические свойства

• (Универсальное хеширование). Семейство функций SWIFFT универсально . Это означает, что для любого фиксированного отдельного $x,x'$, вероятность (при случайном выборе $f$ из семьи), что $f(x)=f(x')$ является обратной величиной размера диапазона.
• (Регулярность). Семейство функций сжатия SWIFFT является регулярным. Функция $f$ называется регулярным, если для входного $x$ выбранных равномерно случайным образом из области определения, выход $f(x)$ распределяется равномерно по диапазону.
• (экстрактор случайностей). SWIFFT — это экстрактор случайных чисел . Для хеш-таблиц и связанных с ними приложений обычно желательно, чтобы выходные данные хеш-функции распределялись равномерно (или как можно ближе к равномерному), даже если входные данные не являются однородными. Хэш-функции, дающие такие гарантии, известны как экстракторы случайности , поскольку они очищают неравномерную случайность входных данных до (почти) равномерно распределенных выходных данных. Формально извлечение случайности на самом деле является свойством семейства функций, из которого случайным образом (и не обращая внимания на входные данные) выбирается одна функция.

и

• SWIFFT не является псевдослучайным из-за линейности. Для любой функции $f$ от нашей семьи и любых двух входов $x_{1}$, $x_{2}$ такой, что $x_{1}+x_{2}$ также является допустимым вводом, у нас есть это $f(x_{1})+f(x_{2})=f(x_{1}+x_{2})$. Это соотношение вряд ли будет соблюдаться для случайной функции, поэтому злоумышленник может легко отличить наши функции от случайной функции.
• Авторы не утверждают, что функции SWIFFT ведут себя как случайный оракул . Говорят, что функция ведет себя как случайный оракул, если она действует как действительно случайная функция. Это отличается от псевдослучайности тем, что функция фиксированная и общедоступная.
• Семейство SWIFFT доказуемо устойчиво к коллизиям (в асимптотическом смысле) при относительно мягком предположении о наихудшей сложности поиска коротких векторов в циклических/идеальных решетках. Это означает, что семейство также устойчиво ко второму прообразу.

Теоретическая безопасность

SWIFFT — это пример доказуемо безопасной криптографической хэш-функции . Как и большинство доказательств безопасности, доказательство безопасности SWIFFT основано на сведении к определенной трудной для решения математической задаче. Обратите внимание, что это означает, что безопасность SWIFFT во многом зависит от сложности этой математической задачи.

Сведение в случае SWIFFT сводится к проблеме поиска коротких векторов в циклических/ идеальных решетках . Можно доказать, что справедливо следующее:Предположим, у нас есть алгоритм, который для случайной версии SWIFFT, заданной формулой $f$ можно найти коллизии в $f$ в течение некоторого возможного времени $T$, и с вероятностью $p$. Допускается, что алгоритм работает только в небольшой, но заметной части семейства SWIFFT. Тогда мы также можем найти алгоритм $f_{2}$ который всегда может найти короткий вектор в любой идеальной решетке над кольцом $\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ в какое-то возможное время $T_{2}$, в зависимости от $T$ и $p$.Это означает, что поиск коллизий в SWIFFT по меньшей мере так же сложен, как и наихудший сценарий поиска коротких векторов в решетке по $\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$. На данный момент все самые быстрые алгоритмы поиска коротких векторов являются экспоненциальными. $n$. Обратите внимание, что это гарантирует отсутствие значительного набора «слабых случаев», в которых безопасность SWIFFT является слабой. Эту гарантию не дают большинство других доказуемо безопасных хеш-функций.

Практическая безопасность

Известные рабочие атаки — это обобщенная атака дня рождения , которая занимает 2 ¹⁰⁶ операции и инверсионные атаки, которые занимают 2 ⁴⁴⁸ операции по выбору стандартных параметров. Обычно этого считается достаточным, чтобы сделать атаку противника невозможной.