En criptografía , un predicado estricto 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 un algoritmo probabilístico de tiempo polinómico (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 dibuja uniformemente al azar, entonces se daf (x) , cualquier adversario de PPT solo puede distinguir el bit b (x) de núcleo duro 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 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 de núcleo duro captura "en un sentido concentrado" la dureza de invertir f .
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, si bien 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 fundamental 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 . Deje x j denotar el j ésimo bit de x y r j el j ésimo bit de r . Luego
es un predicado fundamental de g . Tenga en cuenta que b (x, r) = < x, r > donde <·, ·> denota el producto interno estándar en el espacio vectorial ( Z 2 ) n . Este predicado es fundamental debido a problemas de cálculo; es decir, no es difícil de calcular porque g (x, r) es información teóricamente con pérdidas. Por el contrario, 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 bits de salida O (log | x |) . Suponga 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 . Dejar
Entonces h (x, r) : = b 1 (x, r) b 2 (x, r) ... b l (| x |) (x, r) es una función de núcleo duro con una longitud de salida l (| x |) . [6]
A veces ocurre que una parte 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 fundamental de RSA y los bloques de O (log | x |) bits de x son indistinguibles de las cadenas de bits aleatorias en tiempo polinómico (bajo el supuesto de que la función RSA es difícil de invertir). [7]
Los predicados de núcleo duro dan 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
es una secuencia de bits pseudoaleatoria, donde f n significa la n-ésima iteración de aplicar 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 trampilla (conocidos como predicados de trampilla ) se pueden utilizar para construir esquemas de cifrado de clave pública semánticamente seguros . [1] : 129
Ver también
- 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 se puede ver como un algoritmo para decodificar listas del código Hadamard ).
Referencias
- ^ a b c d Goldwasser, S. y Bellare, M. "Notas de la conferencia sobre criptografía" . Curso de verano sobre criptografía, MIT, 1996-2001
- ^ Definición 2.4 en Lindell, Yehuda. "Fundamentos de la criptografía 89-856" (PDF) . Ciencias de la Computación, Universidad Bar Ilan . Universidad Bar Ilan . Consultado el 11 de enero de 2016 .
- ^ FoC de Goldreich, vol 1, def 2.5.5.
- ^ Definición 3 en Holenstein, Thomas; et al. "Clasificación completa de funciones bilineales Hard-Core" (PDF) . IACR eprint . IACR . Consultado el 11 de enero de 2016 .
- ^ O. Goldreich y LA Levin, Un predicado de núcleo duro para todas las funciones unidireccionales, STOC 1989, pp25-32.
- ^ FoC de Goldreich, vol 1, Teorema 2.5.6.
- ^ J. Håstad , M. Naslund, La seguridad de todos los RSA y bits de registro discretos (2004) : Journal of the ACM, 2004.
- Oded Goldreich, Fundamentos de la criptografía vol 1: Herramientas básicas , Cambridge University Press, 2001.