RÁPIDO

En criptografía , SWIFFT es una colección de funciones hash con seguridad demostrable . Se basa en el concepto de la transformada rápida de Fourier (FFT). SWIFFT no es la primera función hash basada en la FFT, pero se distingue por proporcionar una prueba matemática de su seguridad. Se puede demostrar que encontrar colisiones en SWIFFT es al menos tan difícil como encontrar vectores cortos en retículos cíclicos/ideales en el peor de los casos . Al proporcionar una reducción de seguridad al peor caso de un problema matemático complejo, SWIFFT ofrece una garantía de seguridad mucho más sólida que la mayoría de las demás funciones hash criptográficas .

A diferencia de muchas otras funciones hash con seguridad demostrable, el algoritmo es bastante rápido, alcanzando un rendimiento de 40  Mbit/s en un procesador  Intel Pentium 4 de 3,2 GHz. Si bien SWIFFT cumple con muchas propiedades criptográficas y estadísticas deseables, no fue diseñado para ser una función hash criptográfica de uso general. Por ejemplo, no es una función pseudoaleatoria y no sería una instancia adecuada de un oráculo aleatorio . El algoritmo es menos eficiente que la mayoría de las funciones hash tradicionales que no ofrecen una prueba de su resistencia a colisiones. Por lo tanto, su uso práctico se centraría principalmente en aplicaciones donde la prueba de resistencia a colisiones es particularmente valiosa, como las firmas digitales que deben mantener su fiabilidad durante un largo período.

Se propuso una modificación de SWIFFT llamada SWIFFTX como candidata a función SHA-3 en la competición de funciones hash del NIST ^{[ 1 ]} y fue rechazada en la primera ronda. ^{[ 2 ]}

El algoritmo es el siguiente: ^{[ 3 ]}

1. Llamemos α a la variable polinómica .
2. Entrada : mensaje M de longitud mn
3. Convierta M en una colección de polinomios p ₁ , … , p _m en un cierto anillo de polinomios R con coeficientes binarios.
4. Calcula los coeficientes de Fourier de cada p _i usando SWIFFT.
5. Defina los coeficientes de Fourier de a _i , de modo que sean fijos y dependan de una familia de SWIFFT.
6. Multiplique punto por punto los coeficientes de Fourier p _i con los coeficientes de Fourier de a _i para cada i .
7. Utilice la transformada rápida de Fourier inversa para obtener m polinomios f _i de grado < 2 n .
8. Calcular${\displaystyle f=\sum _{i=1}^{m}(f_{i})}$módulo p y α ⁿ + 1 .
9. Convierte f a n log( p ) bits y muéstralo .

La operación FFT del paso 4 es fácil de invertir y se realiza para lograr la difusión , es decir, para mezclar los bits de entrada. La combinación lineal del paso 6 logra la confusión , ya que comprime la entrada. Esta es solo una descripción general del funcionamiento del algoritmo; se utilizan optimizaciones más avanzadas para obtener finalmente un algoritmo de alto rendimiento.

Las funciones SWIFFT se pueden describir como una expresión algebraica simple sobre un anillo de polinomios R. Una familia de estas funciones depende de tres parámetros principales: sea n una potencia de 2, sea m > 0 un entero pequeño y sea p > 0 un módulo (no necesariamente primo , pero es conveniente elegirlo primo). Definimos R como el anillo R = ℤ _p [ α ]/( α ⁿ + 1) , es decir, el anillo de polinomios en α con coeficientes enteros, módulo p y α ⁿ + 1 . Un elemento de R se puede escribir como un polinomio de grado < n con coeficientes en ℤ _p . Una determinada función en la familia SWIFFT se especifica mediante m elementos fijos a ₁ , … , a _m ∈ R del anillo.${\displaystyle R}$, que se denominan multiplicadores. La función corresponde a la siguiente fórmula sobre R :

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

Los x ₁ , … , x _m ∈ R son polinomios con coeficientes binarios, y corresponden a la entrada binaria de longitud mn .

Para calcular la expresión anterior, el problema principal consiste en calcular los productos polinomiales a _i ⋅ x _i . Una forma rápida de calcular estos productos la proporciona el teorema de convolución . Este teorema establece que, bajo ciertas restricciones, F { f ∗ g } = F { f } ⋅ F { g } , donde F denota la transformada de Fourier y ⋅ denota el producto punto a punto. En el caso general del teorema de convolución, ∗ no denota multiplicación, sino convolución . Sin embargo, se puede demostrar que la multiplicación de polinomios es una convolución.

Los parámetros m , p y n están sujetos a las siguientes restricciones:

• n debe ser una potencia de 2,
• p debe ser primo,
• p − 1 debe ser un múltiplo de 2 n , y
• log( p ) < m (de lo contrario, la salida no será menor que la entrada).

Una posible opción es ( n , m , p ) = (64,16,257) , que logra un rendimiento de aproximadamente 40  Mbit/s, una seguridad de aproximadamente 2 ¹⁰⁶ operaciones para encontrar colisiones y un tamaño de resumen de 512 bits.

• Hashing universal. La familia de funciones SWIFFT es universal . Esto significa que para cualquier x e y distintos fijos , la probabilidad (sobre la elección aleatoria de f de la familia) de que f ( x ) = f ( y ) es la inversa del tamaño del rango.
• Regularidad. La familia de funciones de compresión SWIFFT es regular. Se dice que una función f es regular si, para una entrada x elegida uniformemente al azar del dominio, la salida f ( x ) se distribuye uniformemente en el rango.
• Extractor de aleatoriedad. SWIFFT es un extractor de aleatoriedad . Para tablas hash y aplicaciones relacionadas, suele ser deseable que las salidas de la función hash se distribuyan uniformemente (o lo más uniformemente posible), incluso cuando las entradas no lo son. Las funciones hash que ofrecen tales garantías se conocen como extractores de aleatoriedad , ya que reducen la aleatoriedad no uniforme de la entrada a una salida con distribución (casi) uniforme. Formalmente, la extracción de aleatoriedad es en realidad una propiedad de una familia de funciones, de la cual se elige una función al azar (sin tener en cuenta la entrada).

• SWIFFT no es pseudoaleatorio debido a su linealidad. Para cualquier función f de nuestra familia y cualesquiera dos entradas x e y tales que x + y también sea una entrada válida, se cumple que f ( x ) + f ( y ) = f ( x + y ) . Es muy improbable que esta relación se cumpla para una función aleatoria, por lo que un adversario puede distinguir fácilmente nuestras funciones de una función aleatoria.
• Los autores no afirman que las funciones SWIFFT se comporten como un oráculo aleatorio . Se dice que una función se comporta como un oráculo aleatorio si actúa como una función verdaderamente aleatoria. Esto difiere de la pseudoaleatoriedad en que la función es fija y pública.
• La familia SWIFFT es demostrablemente resistente a colisiones (en un sentido asintótico), bajo una suposición relativamente leve sobre la dificultad en el peor de los casos de encontrar vectores cortos en retículos cíclicos/ideales . Esto implica que la familia también es resistente a la segunda preimagen.