Función pseudoaleatoria de Naor-Reingold

En 1997, Moni Naor y Omer Reingold describieron construcciones eficientes para varias primitivas criptográficas en criptografía de clave privada y de clave pública . Su resultado es la construcción de una función pseudoaleatoria eficiente . Sean p y l números primos con l | p −1. Seleccione un elemento g ∈${\displaystyle {\mathbb {F} _{p}}^{*}}$de orden multiplicativo l . Entonces, para cada vector (n+1) -dimensional a = ( a ₀ ,a ₁ , ..., a _n )∈${\displaystyle (\mathbb {F} _{l})^{n+1}}$definen la función

$${\displaystyle f_{a}(x)=g^{a_{0}\cdot a_{1}^{x_{1}}a_{2}^{x_{2}}...a_{n}^{x_{n}}}\in \mathbb {F} _{p}}$$

donde x  = x ₁ ... x _n es la representación en bits del entero x , 0  ≤ x ≤ 2 ^{n −1} , con algunos ceros iniciales adicionales si es necesario. ^{[ 1 ]}

Sea p  = 7 y l  = 3; entonces l | p −1. Seleccione g  = 4 ∈${\displaystyle {\mathbb {F} _{7}}^{*}}$de orden multiplicativo 3 (ya que 4 ³ = 64 ≡ 1 mod  7). Para n  = 3, a  = (1, 1, 2, 1) y x  = 5 (la representación en bits de 5 es 101), podemos calcular${\displaystyle f_{a}(5)}$como sigue:

$${\displaystyle f_{a}(x)=g^{a_{0}\cdot a_{1}^{x_{1}}a_{2}^{x_{2}}...a_{n}^{x_{n}}}\in \mathbb {F} _{p}}$$

$${\displaystyle f_{a}(5)=4^{1\cdot 1^{1}2^{0}1^{1}}=4^{1}=4\in \mathbb {F} _{7}}$$

La evaluación de la función${\displaystyle f_{a}(x)}$En la construcción de Naor-Reingold se puede hacer de forma muy eficiente. Calcular el valor de la función${\displaystyle f_{a}(x)}$En cualquier punto dado, es comparable con una exponenciación modular y n multiplicaciones modulares. Esta función puede calcularse en paralelo mediante circuitos umbral de profundidad limitada y tamaño polinomial.

La función de Naor-Reingold puede utilizarse como base de muchos esquemas criptográficos , incluidos el cifrado simétrico , la autenticación y las firmas digitales .

Supongamos que un atacante ve varias salidas de la función, por ejemplo:${\displaystyle f_{a}(1)=g^{a_{1}},f_{a}(2)=g^{a_{2}},f_{a}(3)=g^{a_{1}a_{2}}}$, ...${\displaystyle f_{a}(k)=g^{a_{1}^{x_{1}}a_{2}^{x_{2}}...a_{n}^{x_{n}}}}$y quiere calcular${\displaystyle f_{a}(k+1)}$Supongamos, para simplificar, que x ₁ = 0, entonces el atacante necesita resolver el problema computacional Diffie-Hellman (CDH) entre${\displaystyle f_{a}(1)=g^{a_{1}}}$y${\displaystyle f_{a}(k)=g^{a_{2}^{x_{2}}...a_{n}^{x_{n}}}}$Llegar${\displaystyle f_{a}(k+1)=g^{a_{1}a_{2}^{x_{2}}\dots a_{n}^{x_{n}}}}$En general, pasar de k a k + 1 cambia el patrón de bits y, a menos que k + 1 sea una potencia de 2, se puede dividir el exponente en${\displaystyle f_{a}(k+1)}$De modo que el cálculo corresponde a calcular la clave Diffie-Hellman entre dos de los resultados anteriores. Este atacante pretende predecir el siguiente elemento de la secuencia . Un ataque de este tipo sería muy grave, pero también es posible contrarrestarlo trabajando en grupo con un problema Diffie-Hellman difícil (DHP).

Una medida natural de cuán útil puede ser una secuencia para fines criptográficos es el tamaño de su complejidad lineal . La complejidad lineal de una secuencia de n elementos W( x ), x = 0,1,2,..., n – 1, sobre un anillo${\displaystyle {\mathcal {R}}}$es la longitud l de la relación de recurrencia lineal más corta W( x + l ) = A _{l −1} W( x + l −1) + ... + A ₀ W( ​​x ), x = 0,1,2,..., n – l −1 con A ₀ , ..., A _{l −1} ∈${\displaystyle {\mathcal {R}}}$, lo cual se satisface con esta secuencia.

Para algunos${\displaystyle \gamma }$> 0, n ≥ (1+${\displaystyle \gamma }$)${\displaystyle \log l}$, para cualquier${\displaystyle \delta >0}$, suficientemente grande l , la complejidad lineal de la secuencia${\displaystyle f_{a}(x)}$,0 ≤ x ≤ 2 ^n-1 , denotado por${\displaystyle L_{a}}$Satisface

$${\displaystyle L_{a}\geqslant {\begin{cases}l^{1-\ \delta \,\!}&{\text{, si }}\gamma \,\!\geqslant 2\\l^{\left({\tfrac {\ \gamma \,\!}{2-\ \delta \,\!}}\right)}&{\text{, si }}\gamma \,\!<2\end{cases}}}$$

para todos excepto posiblemente como máximo${\displaystyle 3(l-1)^{n-\delta }}$vectores a ∈${\displaystyle (\mathbb {F} _{l})^{n}}$. ^{[ 3 ]} El límite de este trabajo tiene desventajas, a saber, no se aplica al caso muy interesante${\displaystyle \log p\approx \log n\approx {n.}}$

La distribución estadística de${\displaystyle f_{a}(x)}$ es exponencialmente cercana a una distribución uniforme para casi todos los vectores a ∈${\displaystyle (\mathbb {F} _{l})^{n}}$.

Dejar${\displaystyle {\mathbf {D} }_{a}}$sea ​​la discrepancia del conjunto${\displaystyle \{f_{a}(x)|0\leq x\leq 2^{n-1}\}}$. Por lo tanto, si${\displaystyle n=\log p}$es la longitud de bits de p entonces para todos los vectores a ∈${\displaystyle (\mathbb {F} _{l})^{n}}$el límite${\displaystyle {\mathbf {D} }_{a}\leq \Delta (l,p)}$sostiene, donde

$${\displaystyle \Delta (l,p)={\begin{cases}p^{\left({\tfrac {1-\ \gamma \,\!}{2}}\right)}l^{\left({\tfrac {-1}{2}}\right)}\log ^{2}p&{\text{ si }}l\geqslant p^{\gamma \,\!}\\p^{\left({\tfrac {1}{2}}\right)}l^{-1}\log ^{2}p&{\text{ si }}p^{\gamma \,\!}>l\geqslant p^{\left({\tfrac {2}{3}}\right)}\\p^{\left({\tfrac {1}{4}}\right)}l^{\left({\tfrac {-5}{8}}\right)}\log ^{2}p&{\text{ si }}p^{\left({\tfrac {2}{3}}\right)}>l\geqslant p^{\left({\tfrac {1}{2}}\right)}\\p^{\left({\tfrac {1}{8}}\right)}l^{\left({\tfrac {-3}{8}}\right)}\log ^{2}p&{\text{ si }}p^{\left({\tfrac {1}{2}}\right)}>l\geqslant p^{\left({\tfrac {1}{3}}\right)}\\\end{cases}}}$$ y $${\displaystyle \gamma =2,5-\log 3=0,9150\cdots }$$

Aunque esta propiedad no parece tener implicaciones criptográficas inmediatas, el hecho inverso, es decir, la distribución no uniforme, de ser cierto, tendría consecuencias desastrosas para las aplicaciones de esta función. ^{[ 4 ]}

La versión de esta función en forma de curva elíptica también es de interés. En particular, puede ayudar a mejorar la seguridad criptográfica del sistema correspondiente. Sea p > 3 un número primo y sea E una curva elíptica sobre${\displaystyle \mathbb {F} _{p}}$, entonces cada vector a define una secuencia finita en el subgrupo${\displaystyle \langle G\rangle }$como: $${\displaystyle F_{a}(x)=(a_{1}^{x_{1}}a_{2}^{x_{2}}\dots a_{n}^{x_{n}})G}$$

dónde${\displaystyle x=x_{1}\dots x_{n}}$ es la representación en bits de un entero${\displaystyle x,0\leq x\leq 2^{n-1}}$La secuencia de curvas elípticas de Naor-Reingold se define como $${\displaystyle u_{k}=X(f_{a}(k))\;{\mbox{where }}X(P){\mbox{ is the abscissa of}}\;P\in E.}$$^{[ 5 ]}

Si se cumple el supuesto de decisión de Diffie-Hellman , el índice k no es suficiente para calcular${\displaystyle u_{k}}$en tiempo polinomial, incluso si un atacante realiza un número polinomial de consultas a un oráculo aleatorio.

• Supuesto de Diffie-Hellman para la toma de decisiones
• Campo finito
• Generador congruencial inverso
• Números pseudoaleatorios congruenciales inversos generalizados

• Naor, Moni; Reingold, Omer (2004), "Construcciones basadas en la teoría de números de funciones pseudoaleatorias eficientes", Journal of the Association for Computing Machinery , 51 (2): 231– 262, doi : 10.1145/972639.972643 , S2CID 8665271 .
• Shparlinski, Igor (2003), Aplicaciones criptográficas de la teoría analítica de números: límites inferiores de complejidad y pseudorandomness (primera  ed.), Birkhäuser Basel, ISBN 978-3-7643-6654-4
• Goldreich, Oded (1998), Criptografía moderna, pruebas probabilísticas y pseudorandomness (primera  ed.), Springer, ISBN 978-3-540-64766-9