SWIFFT

SWIFFT — набор криптографических хеш-функций с доказанной стойкостью^[1][2][3]. Они основываются на быстром преобразовании Фурье (БПФ, англ. Fast Fourier Transform, FFT) и используют алгоритм LLL-редуцированных базисов^[англ.]. Криптографическая стойкость функций SWIFFT (в асимптотическом смысле)^[4] математически доказана при использовании рекомендуемых параметров^[5]. Поиск коллизий в SWIFFT в худшем случае требует не меньше временных затрат, чем нахождение коротких векторов в циклических/идеальных решётках. Практическое применение SWIFFT будет ценно именно в тех случаях, когда стойкость к коллизиям особенно важна. Например, цифровые подписи, которые должны оставаться надёжными длительное время.

Данный алгоритм обеспечивает пропускную способность порядка 40 Мб/с на процессоре Intel Pentium 4 с тактовой частотой 3,2 ГГц^[6][1]. Было проведено исследование, направленное на ускорение БПФ, которое используется в SWIFFT^[7]. Как результат, скорость работы алгоритма удалось увеличить более чем в 13 раз^[6]. Данная реализация SWIFFT оказалась быстрее, чем реализации широко распространенных хеш-функций^[8].

На конкурсе Национального института стандартов и технологий США^[2] 2012 года был предложен SWIFFTX (модификация SWIFFT) в качестве SHA-3 (на замену более старых SHA-2 и особенно SHA-1^[9]), но был отклонён в первом раунде^[10].

1. ↑ ^{1 2} Lyubashevsky et al., 2008.
2. ↑ ^{1 2} Arbitman et al., 2008.
3. ↑ Györfi et al., 2012, с. 2.
4. ↑ Arbitman et al., 2008, с. 1.
5. ↑ Buchmann, Lindner, 2009, с. 1-2.
6. ↑ ^{1 2} Györfi et al., 2012, с. 15.
7. ↑ Györfi et al., 2012, с. 15-16.
8. ↑ Györfi et al., 2012, с. 16.
9. ↑ PRE- SHA-3 COMPETITION  (неопр.). National Institute of Standards and Technology (15 апреля 2005). Архивировано 9 августа 2017 года.
10. ↑ Second Round Candidates  (неопр.). National Institute of Standards and Technology (19 января 2010). Дата обращения: 14 февраля 2010. Архивировано 10 апреля 2012 года.