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 ∈ de orden multiplicativo l . Luego, para cada vector (n+1) -dimensional a = ( a ₀ ,a ₁ , ..., a _n )∈ , definen la función ${\displaystyle {\mathbb {F} _{p}}^{*}}$ ${\displaystyle (\mathbb {F} _{l})^{n+1}}$

${\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]

Ejemplo

Sea p  = 7 y l  = 3; por lo tanto , l | p −1. Seleccione g  = 4 ∈ 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 de la siguiente manera: ${\displaystyle {\mathbb {F} _{7}}^{*}}$ ${\displaystyle f_{a}(5)}$

${\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}}$

Eficiencia

La evaluación de una función en la construcción de Naor-Reingold se puede realizar de manera muy eficiente. El cálculo del valor de la función en cualquier punto dado es comparable con una exponenciación modular y multiplicaciones n-modulares. Esta función se puede calcular en paralelo mediante circuitos de umbral de profundidad limitada y tamaño polinomial. ${\displaystyle f_{a}(x)}$ ${\displaystyle f_{a}(x)}$

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

Seguridad de la función

Supongamos que un atacante ve varias salidas de la función, p. ej ., ... y quiere calcular . Supongamos para simplificar que x ₁ = 0, entonces el atacante necesita resolver el Diffie–Hellman computacional (CDH) entre y para obtener . 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 de modo que el cálculo corresponda al cálculo de la clave Diffie–Hellman entre dos de los resultados anteriores. Este atacante quiere predecir el siguiente elemento de la secuencia . Un ataque de este tipo sería muy malo, pero también es posible combatirlo trabajando en grupos con un problema Diffie–Hellman difícil (DHP). ${\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}}}}$ ${\displaystyle f_{a}(k+1)}$ ${\displaystyle f_{a}(1)=g^{a_{1}}}$ ${\displaystyle f_{a}(k)=g^{a_{2}^{x_{2}}...a_{n}^{x_{n}}}}$ ${\displaystyle f_{a}(k+1)=g^{a_{1}a_{2}^{x_{2}}\dots a_{n}^{x_{n}}}}$ ${\displaystyle f_{a}(k+1)}$

Ejemplo: Un atacante ve varias salidas de la función p. ej ., como en el ejemplo anterior, y . Luego, el atacante quiere predecir el siguiente elemento de secuencia de esta función, . Sin embargo, el atacante no puede predecir el resultado de a partir de conocer y . ${\displaystyle f_{a}(5)=4^{1^{1}2^{0}1^{1}}=4^{1}=4}$ ${\displaystyle f_{a}(1)=4^{1^{0}2^{0}1^{1}}=4^{1}=4}$ ${\displaystyle f_{a}(6)}$ ${\displaystyle f_{a}(6)}$ ${\displaystyle f_{a}(1)}$ ${\displaystyle f_{a}(5)}$

Existen otros ataques que serían muy malos para un generador de números pseudoaleatorios : el usuario espera obtener números aleatorios de la salida, por lo que, por supuesto, el flujo no debería ser predecible, pero aún más, debería ser indistinguible de una cadena aleatoria. Sea α el algoritmo con acceso a un oráculo para evaluar la función . Supongamos que el supuesto decisional de Diffie-Hellman se cumple para , Naor y Reingold demuestran que para cada algoritmo de tiempo polinomial probabilístico y n suficientemente grande ${\displaystyle {\mathcal {A}}^{f}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle f_{a}(x)}$ ${\displaystyle \mathbb {F} _{p}}$ ${\displaystyle {\mathcal {A}}}$

${\displaystyle {\text{Pr }}[{\mathcal {A}}^{f_{a}(x)}(p,g)\to 1]-{\text{Pr }}[{\mathcal {A}}^{R}(p,g)\to 1]}$ es insignificante .

La primera probabilidad se toma sobre la elección de la semilla s = (p, g, a) y la segunda probabilidad se toma sobre la distribución aleatoria inducida en p, g por , el generador de instancias y la elección aleatoria de la función entre el conjunto de todas las funciones. ^[2] ${\displaystyle {\mathcal {I}}{\mathcal {G}}(n)}$ ${\displaystyle R_{a}(x)}$ ${\displaystyle \{0,1\}^{n}\to \mathbb {F} _{p}}$

Complejidad lineal

Una medida natural de cuán útil puede ser una secuencia para propósitos 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 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} ∈ , que se satisface por esta secuencia. ${\displaystyle {\mathcal {R}}}$ ${\displaystyle {\mathcal {R}}}$

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

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

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

Uniformidad de distribución

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

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

${\displaystyle \Delta (l,p)={\begin{cases}p^{\left({\tfrac {1-\ \gamma \,\!}{2}}\right)}l^{\left({\tfrac {-1}{2}}\right)}\log ^{2}p&{\text{ if }}l\geqslant p^{\gamma \,\!}\\p^{\left({\tfrac {1}{2}}\right)}l^{-1}\log ^{2}p&{\text{ if }}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{ if }}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{ if }}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, si fuera cierto tendría consecuencias desastrosas para las aplicaciones de esta función. ^[4]

Secuencias en curva elíptica

La versión de curva elíptica de esta función también es interesante. En particular, puede ayudar a mejorar la seguridad criptográfica del sistema correspondiente. Sea p > 3 primo y sea E una curva elíptica sobre , entonces cada vector a define una secuencia finita en el subgrupo como: ${\displaystyle \mathbb {F} _{p}}$ ${\displaystyle \langle G\rangle }$

${\displaystyle F_{a}(x)=(a_{1}^{x_{1}}a_{2}^{x_{2}}\dots a_{n}^{x_{n}})G}$

donde es la representación en bits del entero . La secuencia de curvas elípticas de Naor-Reingold se define como ${\displaystyle x=x_{1}\dots x_{n}}$ ${\displaystyle x,0\leq x\leq 2^{n-1}}$

${\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 decisional de Diffie-Hellman , el índice k no es suficiente para calcular en tiempo polinomial, incluso si un atacante realiza una cantidad polinomial de consultas a un oráculo aleatorio.https://en.wikipedia.org/wiki/Naor-Reingold_Pseudorandom_Function/Elliptic_curve ${\displaystyle u_{k}}$

Véase también

• Supuesto decisional de Diffie-Hellman
• Campo finito
• Generador congruencial inverso
• Números pseudoaleatorios congruenciales inversos generalizados

Notas

1. Naor, M., Reingold, O. "Construcciones teóricas de números de funciones pseudoaleatorias eficientes", Proc 38th IEEE Symp. on Foundations of Comp. Sci, (1997), 458–467.
2. Boneh, Dan. "El problema de decisión Diffie-Hellman", ANTS-III: Actas del Tercer Simposio Internacional sobre Teoría Algorítmica de Números, 1998, 48-63.
3. Shparlinski, Igor E. "Complejidad lineal de la función pseudoaleatoria Naor-Reingold", Inform. Process Lett, 76 (2000), 95–99.
4. Shparlinski, Igor E. "Sobre la uniformidad de la distribución de la función pseudoaleatoria Naor-Reingold", Campos finitos y sus aplicaciones, 7 (2001), 318-326
5. Cruz, M., Gomez, D., Sadornil, D. "Sobre la complejidad lineal de la secuencia de Naor-Reingold con curvas elípticas", Campos finitos y sus aplicaciones, 16 (2010), 329–333

Referencias

• Naor, Moni; Reingold, Omer (2004), "Construcciones teóricas 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 pseudoaleatoriedad (primera edición), Birkhäuser Basel, ISBN 978-3-7643-6654-4
• Goldreich, Oded (1998), Criptografía moderna, pruebas probabilísticas y pseudoaleatoriedad (primera edición), Springer, ISBN 978-3-540-64766-9