Predicado de núcleo duro

En criptografía , un predicado de núcleo duro de una función unidireccional f es un predicado b (es decir, una función cuya salida es un solo bit) que es fácil de calcular (como una función de x ) pero es difícil de calcular dado f(x) . En términos formales, no existe un algoritmo de tiempo polinomial probabilístico (PPT) que calcule b(x) a partir de f(x) con una probabilidad significativamente mayor que la mitad sobre la elección aleatoria de x . ^{[1] : 34} En otras palabras, si x se extrae uniformemente al azar, entonces dado f(x) , cualquier adversario de PPT solo puede distinguir el bit de núcleo duro b(x) y un bit uniformemente aleatorio con una ventaja insignificante sobre la longitud de x . ^[2]

Una función de núcleo duro se puede definir de manera similar. Es decir, si x se elige de manera uniforme al azar, entonces, dada f(x) , cualquier algoritmo PPT solo puede distinguir el valor de la función de núcleo duro h(x) y los bits uniformemente aleatorios de longitud |h(x)| con una ventaja insignificante sobre la longitud de x . ^{[3] [4]}

Un predicado duro captura "en un sentido concentrado" la dureza de invertir f .

Si bien es difícil invertir una función unidireccional, no existen garantías sobre la viabilidad de calcular información parcial sobre la preimagen c a partir de la imagen f(x) . Por ejemplo, si bien se supone que RSA es una función unidireccional, el símbolo de Jacobi de la preimagen se puede calcular fácilmente a partir del de la imagen. ^{[1] : 121}

Está claro que si una función unidireccional tiene un predicado de núcleo duro, entonces debe ser unidireccional. Oded Goldreich y Leonid Levin (1989) mostraron cómo cada función unidireccional puede modificarse trivialmente para obtener una función unidireccional que tiene un predicado de núcleo duro específico. ^[5] Sea f una función unidireccional. Defina g(x,r) = (f(x), r) donde la longitud de r es la misma que la de x . Sea x _j el j ^-ésimo bit de x y r _j el j ^-ésimo bit de r . Entonces

${\displaystyle b(x,r):=\langle x,r\rangle =\bigoplus _{j}x_{j}r_{j}}$

es un predicado de núcleo duro de g . Nótese que b(x, r) = < x, r > donde <·, ·> denota el producto interno estándar en el espacio vectorial ( Z ₂ ) ⁿ . Este predicado es de núcleo duro debido a cuestiones computacionales; es decir, no es difícil de calcular porque g(x, r) es información teóricamente con pérdida. Más bien, si existe un algoritmo que calcula este predicado de manera eficiente, entonces hay otro algoritmo que puede invertir f de manera eficiente.

Una construcción similar produce una función de núcleo duro con O(log |x|) bits de salida. Supongamos que f es una función unidireccional fuerte. Defina g(x, r) = (f(x), r) donde | r | = 2| x |. Elija una función de longitud l(n) = O(log n) st l(n) ≤ n . Sea

${\displaystyle b_{i}(x,r)=\bigoplus _{j}x_{j}r_{i+j}.}$

Entonces h(x, r)  := b ₁ (x, r) b ₂ (x, r) ... b _l(|x|) (x, r) es una función de núcleo duro con longitud de salida l(|x|) . ^[6]

A veces sucede que un bit real de la entrada x es de núcleo duro. Por ejemplo, cada bit de las entradas a la función RSA es un predicado de núcleo duro de RSA y los bloques de O(log |x|) bits de x son indistinguibles de las cadenas de bits aleatorias en tiempo polinomial (suponiendo que la función RSA es difícil de invertir). ^[7]

Los predicados de núcleo duro permiten construir un generador pseudoaleatorio a partir de cualquier permutación unidireccional . Si b es un predicado de núcleo duro de una permutación unidireccional f y s es una semilla aleatoria, entonces

${\displaystyle \{b(f^{n}(s))\}_{n}}$

es una secuencia de bits pseudoaleatoria, donde f ⁿ significa la n-ésima iteración de aplicación de f en s , y b es el bit de núcleo duro generado por cada ronda n . ^{[1] : 132}

Los predicados de núcleo duro de permutaciones unidireccionales de puerta trampa (conocidos como predicados de puerta trampa ) se pueden utilizar para construir esquemas de cifrado de clave pública semánticamente seguros . ^{[1] : 129}

Véase también

• Descodificación de listas (describe la decodificación de listas; el núcleo de la construcción Goldreich-Levin de predicados de núcleo duro a partir de funciones unidireccionales puede verse como un algoritmo para la decodificación de listas del código Hadamard ).

Referencias

1. Goldwasser, S. y Bellare, M. "Lecture Notes on Cryptography" Archivado el 21 de abril de 2012 en Wayback Machine . Curso de verano sobre criptografía, MIT, 1996-2001
2. Definición 2.4 en Lindell, Yehuda. "Fundamentos de criptografía 89-856" (PDF) . Ciencias de la Computación, Universidad Bar Ilan . Universidad Bar Ilan. Archivado desde el original (PDF) el 19 de enero de 2022. Consultado el 11 de enero de 2016 .
3. FoC de Goldreich, vol 1, def 2.5.5.
4. Definición 3 en Holenstein, Thomas; et al. "Complete Classification of Bilinear Hard-Core Functions" (PDF) . Publicación electrónica de la IACR . IACR . Consultado el 11 de enero de 2016 .
5. O. Goldreich y LA Levin, Un predicado de núcleo duro para todas las funciones unidireccionales, STOC 1989, págs. 25-32.
6. FoC de Goldreich, vol 1, teorema 2.5.6.
7. J. Håstad , M. Naslund, La seguridad de todos los bits de registro discretos y RSA (2004): Revista de la ACM, 2004.

• Oded Goldreich, Fundamentos de criptografía vol 1: Herramientas básicas , Cambridge University Press, 2001.