SWIFFT

редактировать

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

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

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

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

Содержание

1 алгоритм
- 1.1 Пример
2 Алгебраическое описание
3 Вычисление полиномиального произведения
- 3.1 Быстрое преобразование Фурье
- 3.2 Теоретико-числовое преобразование
4 Выбор параметра
5 Статистические свойства
6 Криптографические свойства и безопасность
- 6.1 Теоретическая безопасность
- 6.2 Практическая безопасность
7 Ссылки

Алгоритм

Алгоритм выглядит следующим образом:

Пусть полином вызывается переменная $α {\ displaystyle \ alpha}$ $\ alpha$
Ввод : сообщение $M {\ displaystyle M}$ $M$ длины $mn {\ displaystyle mn}$ $mn$
Преобразовать $M {\ displaystyle M}$ $M$ в набор $m {\ displaystyle m}$ $м$ полиномов $pi {\ displaystyle p_ {i}}$ $p_ {i}$ в определенном кольце многочленов $R {\ displaystyle R}$ $R$ с двоичными коэффициентами.
Вычислить коэффициенты Фурье каждого $pi {\ displaystyle p_ {i}}$ $p_ {i}$ с использованием SWIFFT.
Определить коэффициенты Фурье для $ai { \ displaystyle a_ {i}}$ $a_{i}$ , чтобы они были фиксированными и зависели от семейства SWIFFT.
Точечное умножение коэффициентов Фурье $pi {\ displaystyle p_ {i }}$ $p_ {i}$ с коэффициентами Фурье $ai {\ displaystyle a_ {i}}$ $a_{i}$ для каждого $i {\ displaystyle i}$ $i$ .
Используйте обратное БПФ для получения $m {\ displaystyle m}$ $м$ многочлены $fi {\ displaystyle f_ {i}}$ $f_ {i}$ степени $< 2 n {\displaystyle <2n}$ $<2n$ .
Compute $f = ∑ i = 1 m (fi) {\ displaystyle f = \ sum _ {i = 1} ^ {m} (f_ {i})}$ $f = \ sum _ {{i = 1}} ^ {m} (f_ {i})$ по модулю $p {\ displaystyle p}$ $p$ и $α n + 1 {\ displaystyle \ alpha ^ {n} +1}$ $\ alpha ^ {n} +1$ .
Преобразовать $f {\ displaystyle f}$ $f$ в $n log ⁡ (p) {\ displaystyle n \ log (p)}$ $n \ log (p)$ бит и вывод it.

Операцию FFT на шаге 4 легко инвертировать, и она выполняется для достижения диффузия, то есть до m ix входные биты.
линейная комбинация на шаге 6 приводит к путанице, поскольку она сжимает входные данные.
Это просто высокий уровень Описание того, что делает алгоритм, используются некоторые более сложные оптимизации, чтобы наконец получить высокопроизводительный алгоритм.

Пример

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

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

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

$∑ i = 1 m (ai ⋅ xi) {\ displaystyle \ sum _ {i = 1} ^ {m} (a_ {i} \ cdot x_ {i })}$ $\ sum _ {{i = 1}} ^ {m} (a_ {i} \ cdot x_ {i})$

$x 1,…, xm ∈ R {\ displaystyle x_ {1}, \ ldots, x_ {m} \ in R}$ $x_ {1}, \ ldots, x_ {m } \ in R$ являются многочленами с двоичными коэффициентами, и соответствующий двоичному входу длины $mn {\ displaystyle mn}$ $mn$ .

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

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

F {f * g} = F {f} ⋅ F {g} {\ displaystyle {\ mathcal {F}} \ {f * g \} = {\ mathcal {F}} \ {f \} \ cdot {\ mathcal {F}} \ {g \}}

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

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

Быстрое преобразование Фурье

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

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

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

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

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

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

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

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

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

Криптографические свойства и безопасность

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

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

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

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

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

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

Источники

^Даниэле Миччансио; Юрий Арбитман; Гил Догон; Вадим Любашевский; Крис Пайкерт; Алон Розен (30.10.2008). «SWIFFTX: Предложение по стандарту SHA-3» (PDF). Проверено 3 марта 2017 г.
^«Кандидаты во второй тур». Национальный институт стандартов и технологий. 2009-07-16. Архивировано 4 июня 2017 года. Проверено 3 марта 2017 г. CS1 maint: BOT: статус исходного URL-адреса неизвестен (ссылка )
^Вадим Любашевский; Даниэле Миччансио; Крис Пайкерт; Алон Розен (21 февраля 2008 г.). «SWIFFT: скромное предложение по хешированию FFT» (PDF). Дата обращения 03 марта 2017.