Problemas para entender la teoría detrás de las funciones despreciables y sus aplicaciones en criptografía

Question

Fui enseñado formalmente que:

$\epsilon$ es una función $\epsilon\colon \mathbb{Z^{\geq0}}\rightarrow \mathbb{R^{\geq0}}$ y si $\exists$d: $\epsilon$ ($\lambda$) $\geq \frac{1}{\lambda^{d}}$ entonces $\epsilon$ es no despreciable, y si $\forall$d, $\lambda \geq \lambda_{d}$: $\epsilon(\lambda) \leq \frac{1}{\lambda^{d}}$ entonces $\epsilon$ es despreciable.

Ahora estoy teniendo dificultades para entender algunas cosas:

1) Cuando $\epsilon$ es no despreciable, ¿esto significa que nuestro generador de seudo-aleatorios no funciona bien, verdad? Esencialmente, ¿esto quiere decir que algún adversario puede predecir nuestra clave "aleatoria" con una probabilidad mayor a $1/2$?

2) ¿Qué significa $\epsilon:\mathbb{Z^{\geq0}}\longrightarrow \mathbb{R^{\geq0}}$? Estoy empezando a adentrarme en la teoría matemática, y entiendo otras funciones que siguen el mismo procedimiento (es decir, $E\colon M\times K \longrightarrow C$ para encriptación, espacio de mensajes, espacio de claves, y texto cifrado E, M, K y C, respectivamente) pero esta me hace poco sentido.

3) ¿Qué son $\lambda_d$, $\lambda^d$, y $\epsilon (\lambda)$?

También, siempre son bienvenidos los recursos externos.

¡Gracias!

Answer 1

Una función es despreciable si es "suficientemente pequeña" para todos los propósitos prácticos. Por ejemplo, si tienes un procedimiento que puede $\epsilon$-distinguir entre la salida de un PRNG y bits aleatorios, entonces se puede potenciar este procedimiento (repitiéndolo) y obtener un distinguir $1/2$, como mencionas. Este aumento solo funciona si $\epsilon$ no es despreciable, ya que solo se te permite repetir el distinguir original muchas veces de forma polinómica. Esta es la intuición detrás de la definición.

Para definir formalmente cuándo una función $\epsilon$ es despreciable, primero estrechamos nuestros intereses en funciones que toman como entrada un entero no negativo $\lambda$ (el parámetro de seguridad) y producen un número real no negativo $\epsilon(\lambda)$. Este es el significado detrás de la notación $\epsilon \colon \mathbb{Z}^{\geq 0} \longrightarrow \mathbb{R}^{\geq 0}$. El parámetro de seguridad $\lambda$ es un parámetro con el que se mide el rendimiento del criptosistema; por ejemplo, un distinguir debería ejecutarse en tiempo polinómico en $\lambda$.

Una función $\epsilon$ es no despreciable si $\epsilon(\lambda) = \Omega(\lambda^{-d})$ para algún $d \geq 0$. Equivalentemente, hay algún $d \geq 0$ tal que para $\lambda$ suficientemente grande, se cumple que $\epsilon(\lambda) \geq \lambda^{-d}$. Decimos que $\epsilon$ tiene un crecimiento inverso polinómico ($\lambda^d$ es el polinomio en cuestión; es un polinomio en $\lambda$). Aún más formalmente, hay algún $d \geq 0$ y algún $\lambda_0 \in \mathbb{Z}$ tal que para todo $\lambda \geq \lambda_0$, se cumple que $\epsilon(\lambda) \geq \lambda^d$. Por alguna razón, tu definición utiliza el algo confuso $\lambda_d$ (la notación es confusa porque realmente no depende de $d$).

Answer 2

Para responder a la pregunta 2....

La expresión

$$f : A \to B$$

significa "$f$ es una función con dominio $A$ y codominio $B$", y comúnmente se lee como "$f$ es una función de $A$ en $B$".

Las expresiones

$$ \mathbb{Z}^{\geq 0} \qquad \qquad \mathbb{R}^{\geq 0} $$

denotan los conjuntos de enteros no negativos y números reales no negativos respectivamente.

Por lo tanto, la frase

$$ \epsilon : \mathbb{Z}^{\geq 0} \to \mathbb{R}^{\geq 0}$$

está expresando el hecho de que $\epsilon$ se utiliza para denotar una función que convierte enteros no negativos en números reales no negativos.

Corriendo el riesgo de decir lo obvio, para la pregunta 3....

Parece que $\lambda$ se utiliza para denotar un entero no negativo. La expresión

$$ \lambda^d $$

probablemente significa el valor que obtienes al elevarlo a la potencia de $d$, y la expresión

$$ \epsilon(\lambda) $$

significa el valor que obtienes al sustituir $\lambda$ en la función $\epsilon$. Estoy de acuerdo con la otra respuesta en que $\lambda_d$ probablemente es un error tipográfico y se quiso decir $\lambda_0$, donde $\lambda_0$ también expresa un valor entero. (y probablemente has omitido un $\exists \lambda_0$ en algún lugar)

En cuanto a para qué se están usando estas funciones, eso dependería de lo que estés leyendo.