predicado de extremo 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 función de x ) pero difícil de calcular dado f(x) . En términos formales, no existe ningún algoritmo probabilístico de tiempo polinomial (PPT) que calcule b(x) a partir de f(x) con una probabilidad significativamente mayor que la mitad sobre una elección aleatoria de x . ^{[ 1 ] : 34} En otras palabras, si x se extrae uniformemente al azar, entonces dado f(x) , cualquier adversario 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 puede definirse de manera similar. Es decir, si x se elige uniformemente al azar, entonces, dado f(x) , cualquier algoritmo PPT solo puede distinguir el valor de la función de núcleo duro h(x) y bits aleatorios uniformes de longitud |h(x)| con una ventaja insignificante sobre la longitud de x . ^{[ 3 ] [ 4 ]}

Un predicado de núcleo duro captura "en un sentido concentrado" la dificultad de invertir f .

Si bien es difícil invertir una función unidireccional , no hay garantías sobre la viabilidad de calcular información parcial sobre la preimagen c a partir de la imagen f(x) . Por ejemplo, aunque se conjetura 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}

Es evidente que si una función inyectiva tiene un predicado de núcleo duro, entonces debe ser una función unidireccional. Oded Goldreich y Leonid Levin (1989) demostraron cómo toda función unidireccional puede modificarse trivialmente para obtener una función unidireccional que tenga un predicado de núcleo duro específico. ^{[ 5 ]} Sea f una función unidireccional. Definamos 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 fundamental 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 fundamental debido a problemas computacionales; es decir, no es difícil de calcular porque g(x, r) es teóricamente una operación con pérdida de información. Más bien, si existe un algoritmo que calcula este predicado de manera eficiente, entonces existe 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. Definimos g(x, r) = (f(x), r) donde | r | = 2| x |. Elegimos una función de longitud l(n) = O(log n) tal que 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 ]}

En ocasiones, un bit específico 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 bloques de O(log |x|) bits de x son indistinguibles de cadenas de bits aleatorias en tiempo polinomial (bajo el supuesto de que la función RSA es difícil de invertir). ^{[ 7 ]}

Los predicados de núcleo duro proporcionan una forma de 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 aplicar f en s , y b es el bit de núcleo duro generado en cada ronda n . ^{[ 1 ] : 132}

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

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

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