Poco duro

En criptografía , un predicado duro para una función unidireccional es una función que toma el valor 0 o 1, mientras que su valor es fácil de calcular sabiendo y difícil de calcular sabiendo solo . Formalmente, una función polinomialmente computable es un predicado difícil para una función si la variable aleatoria es difícil de calcular a partir de la variable aleatoria , donde es una variable aleatoria uniformemente distribuida en . $F$ $h$ $h(x)$ $X$ $f(x)$ $h_{n}:D_{n}{\xrightarrow[{}]{}}\{0,1\}$ $f_{n}:D_{n}{\xrightarrow[{}]{}}D_{n}$ $h_{n}(\alpha _{n})$ $f_{n}(\alpha _{n})$ $\alpha_{n}$ $D_{n}$

Véase también

Función hash criptográfica

Enlaces

Girsh EA " Complejidad Computacional y Fundamentos de Criptografía " . Un curso de conferencias que describen los conceptos básicos de la complejidad computacional y la criptografía.
Vereshchagin N.K. Apuntes de clase del curso de criptografía.