SWIFFT

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

Определённая функция в семействе SWIFFT задаётся как ${\displaystyle m}$ фиксированных элементов ${\displaystyle a_{1},\ldots ,a_{m}\in R}$ кольца ${\displaystyle R}$, называемых мультипликаторами. Данную функцию над кольцом ${\displaystyle R}$ можно записать в следующем виде:

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

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

Алгоритм работы следующий:[1][12][11]

1. Берётся ${\displaystyle \alpha }$ — неприводимый многочлен над ${\displaystyle \mathbb {Z} [\alpha ]}$
2. На вход подаётся сообщение ${\displaystyle M}$ длины ${\displaystyle mn}$
3. ${\displaystyle M}$ преобразуется в набор из ${\displaystyle m}$ полиномов ${\displaystyle p_{i}}$ в определённом кольце многочленов ${\displaystyle R}$ с двоичными коэффициентами
4. Рассчитываются коэффициенты Фурье для каждого ${\displaystyle p_{i}}$
5. Задаются фиксированные коэффициенты Фурье ${\displaystyle a_{i}}$ в зависимости от семейства SWIFFT
6. Попарно перемножаются коэффициенты Фурье ${\displaystyle p_{i}}$ с ${\displaystyle a_{i}}$ для каждого ${\displaystyle i}$
7. Используется обратное преобразование Фурье для того, чтобы получить ${\displaystyle m}$ многочленов ${\displaystyle f_{i}}$ степени не более ${\displaystyle 2n}$
8. Рассчитается ${\displaystyle f=\sum _{i=1}^{m}(f_{i})}$ по модулю ${\displaystyle p}$ и ${\displaystyle \alpha ^{n}+1}$.
9. ${\displaystyle f}$ преобразуется в ${\displaystyle n\log(p)}$ битов и отправляются их на выход

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

Параметры m,p,n должны удовлетворят следующим требованиям[15]:

• n должен быть степенью двойки
• p должен быть простым числом
• p-1 должно делиться на 2n
• ${\displaystyle \log(p)<}$m

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

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

• SWIFFT не является псевдослучайной функцией из-за линейности[1]. Для произвольной функции ${\displaystyle f}$ из семейства SWIFFT справедливо следующее: для двух входных параметров ${\displaystyle x_{1}}$, ${\displaystyle x_{2}}$ таких, что ${\displaystyle x_{1}+x_{2}}$ тоже может быть входным параметром, выполнено ${\displaystyle f(x_{1})+f(x_{2})=f(x_{1}+x_{2})}$. Выполнение данного соотношения не подходит к случайной функции, и злоумышленник сможет легко отличить нашу функцию от случайной.

• Для семейства функций SWIFFT доказана криптографическая стойкость к коллизиям (в асимптотическом смысле) при относительно умеренном предположении о сложности задачи нахождения коротких векторов в циклических/идеальных решётках в худшем случае. Это значит, что семейство функций SWIFFT также устойчиво к атаке нахождения второго прообраза[4][16].

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