En criptografía , un predicado fundamental 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 es difícil de calcular dada 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 de 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 sólo puede distinguir el bit central b(x) y un bit uniformemente aleatorio con una ventaja insignificante sobre la longitud de x . [2]
Una función básica 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 básica h(x) y bits uniformemente aleatorios de longitud |h(x)| con ventaja insignificante sobre la longitud de x . [3] [4]
Un predicado incondicional 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 incondicional, entonces debe ser 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 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 bit j de x y r j el bit j de r . Entonces
es un predicado central 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 incondicional 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 existe otro algoritmo que puede invertir f de manera eficiente.
Una construcción similar produce una función básica 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 . Dejar
Entonces h(x, r) := b 1 (x, r) b 2 (x, r) ... b l(|x|) (x, r) es una función básica con longitud de salida l(| x|) . [6]
A veces se da el caso de que un bit real de la entrada x sea de núcleo duro. Por ejemplo, cada bit de entrada a la función RSA es un predicado fundamental de RSA y los bloques de O(log |x|) bits de x son indistinguibles de 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 básicos brindan una forma de construir un generador pseudoaleatorio a partir de cualquier permutación unidireccional . Si b es un predicado fundamental de una permutación unidireccional f y s es una semilla aleatoria, entonces
es una secuencia de bits pseudoaleatoria, donde f n significa la ené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 básicos 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
