predicado de núcleo duro

En criptografía , un predicado básico 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 dadof(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 uniformemente al azar, entonces dado f(x) , cualquier algoritmo PPT solo puede distinguir el valor de la función central h(x) y los bits uniformemente aleatorios de longitud |h(x)| con una ventaja despreciable sobre la longitud de x . ^[3]^[4]

Si bien una función unidireccional es difícil de invertir, 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}

Está claro que si una función uno a uno 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 central 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

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

es un predicado de núcleo duro de g . Tenga en cuenta 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 información teóricamente con pérdidas. 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.