SWIFFT

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

На конкурсі Національного інституту стандартів і технологій США [2] 2012 року було запропоновано SWIFFTX (модифікація SWIFFT) в якості SHA-3 (на заміну більш старих SHA-2 і особливо SHA-1[5]), але її було відхилено в першому раунді[6].

Примітки

[ред. | ред. код]
  1. а б Lyubashevsky et al., 2008.
  2. а б в Arbitman et al., 2008.
  3. а б в г д Györfi et al., 2012.
  4. Buchmann, Lindner, 2009.
  5. PRE- SHA-3 COMPETITION. National Institute of Standards and Technology. 15 квітня 2005. Архів оригіналу за 9 серпня 2017.
  6. Second Round Candidates. National Institute of Standards and Technology. 19 січня 2010. Архів оригіналу за 10 квітня 2012. Процитовано 14 лютого 2010.