Prueba del siguiente bit

Método de prueba para probar la aleatoriedad de generadores de números pseudoaleatorios

En criptografía y teoría de la computación , la prueba del siguiente bit ^[1] es una prueba contra generadores de números pseudoaleatorios . Decimos que una secuencia de bits pasa la siguiente prueba de bits en cualquier posición de la secuencia, si cualquier atacante que conozca los primeros bits (pero no la semilla) no puede predecir el st con un poder computacional razonable. ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle (i+1)}$

Declaraciones precisas

Sea un polinomio y una colección de conjuntos que contengan secuencias de bits de longitud. Además, sea la distribución de probabilidad de las cadenas en . ${\displaystyle P}$ ${\displaystyle S=\{S_{k}\}}$ ${\displaystyle S_{k}}$ ${\displaystyle P(k)}$ ${\displaystyle \mu _{k}}$ ${\displaystyle S_{k}}$

Ahora definimos la prueba del siguiente bit de dos maneras diferentes.

Formulación de circuito booleano

Una colección de predicción ^[2] es una colección de circuitos booleanos , de modo que cada circuito tiene menos de puertas y exactamente entradas. Sea la probabilidad de que, al ingresar los primeros bits de una cadena seleccionada aleatoriamente con probabilidad , el circuito prediga correctamente , es decir: ${\displaystyle C=\{C_{k}^{i}\}}$ ${\displaystyle C_{k}^{i}}$ ${\displaystyle P_{C}(k)}$ ${\displaystyle i}$ ${\displaystyle p_{k,i}^{C}}$ ${\displaystyle i}$ ${\displaystyle s}$ ${\displaystyle S_{k}}$ ${\displaystyle \mu _{k}(s)}$ ${\displaystyle s_{i+1}}$

${\displaystyle p_{k,i}^{C}={\mathcal {P}}\left[C_{k}(s_{1}\ldots s_{i})=s_{i+1}\right|s\in S_{k}{\text{ with probability }}\mu _{k}(s)]}$

Ahora, decimos que pasa la prueba del siguiente bit si para cualquier colección de predicción , cualquier polinomio  : ${\displaystyle \{S_{k}\}_{k}}$ ${\displaystyle C}$ ${\displaystyle Q}$

${\displaystyle p_{k,i}^{C}<{\frac {1}{2}}+{\frac {1}{Q(k)}}}$

Máquinas probabilísticas de Turing

También podemos definir la prueba del siguiente bit en términos de máquinas probabilísticas de Turing , aunque esta definición es algo más estricta (véase el teorema de Adleman ). Sea una máquina probabilística de Turing, que trabaja en tiempo polinómico. Sea la probabilidad de que prediga correctamente el st bit, es decir ${\displaystyle {\mathcal {M}}}$ ${\displaystyle p_{k,i}^{\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle (i+1)}$

${\displaystyle p_{k,i}^{\mathcal {M}}={\mathcal {P}}[M(s_{1}\ldots s_{i})=s_{i+1}|s\in S_{k}{\text{ with probability }}\mu _{k}(s)]}$

Decimos que la colección pasa la prueba del siguiente bit si para todos los polinomios , para todos menos para un número finito , para todos : ${\displaystyle S=\{S_{k}\}}$ ${\displaystyle Q}$ ${\displaystyle k}$ ${\displaystyle 0<i<k}$

${\displaystyle p_{k,i}^{\mathcal {M}}<{\frac {1}{2}}+{\frac {1}{Q(k)}}}$

Completitud de la prueba de Yao

La prueba del siguiente bit es un caso particular de la prueba de Yao para secuencias aleatorias y, por lo tanto, pasarla es una condición necesaria para pasar la prueba de Yao . Sin embargo, Yao también le ha mostrado una condición suficiente . ^[1]

Lo demostramos ahora en el caso de la máquina probabilística de Turing, puesto que Adleman ya ha realizado el trabajo de sustituir la aleatorización por la no uniformidad en su teorema . El caso de los circuitos booleanos no puede derivarse de este caso (ya que implica decidir problemas potencialmente indecidibles), pero la demostración del teorema de Adleman puede adaptarse fácilmente al caso de familias de circuitos booleanos no uniformes.

Sea un distintivo para la versión probabilística de la prueba de Yao, es decir, una máquina probabilística de Turing, que se ejecuta en tiempo polinómico, de modo que existe un polinomio tal que para una infinidad de ${\displaystyle {\mathcal {M}}}$ ${\displaystyle Q}$ ${\displaystyle k}$

${\displaystyle |p_{k,S}^{\mathcal {M}}-p_{k,U}^{\mathcal {M}}|\geq {\frac {1}{Q(k)}}}$

Dejar . Tenemos: y . Entonces, nos damos cuenta de eso . Por lo tanto, al menos uno de ellos no debe ser menor que . ${\displaystyle R_{k,i}=\{s_{1}\ldots s_{i}u_{i+1}\ldots u_{P(k)}|s\in S_{k},u\in \{0,1\}^{P(k)}\}}$ ${\displaystyle R_{k,0}=\{0,1\}^{P(k)}}$ ${\displaystyle R_{k,P(k)}=S_{k}}$ ${\displaystyle \sum _{i=0}^{P(k)}|p_{k,R_{k,i+1}}^{\mathcal {M}}-p_{k,R_{k,i}}^{\mathcal {M}}|\geq |p_{k,R_{k,P(k)}}^{\mathcal {M}}-p_{k,R_{k,0}}^{\mathcal {M}}|=|p_{k,S}^{\mathcal {M}}-p_{k,U}^{\mathcal {M}}|\geq {\frac {1}{Q(k)}}}$ ${\displaystyle |p_{k,R_{k,i+1}}^{\mathcal {M}}-p_{k,R_{k,i}}^{\mathcal {M}}|}$ ${\displaystyle {\frac {1}{Q(k)P(k)}}}$

A continuación, consideramos las distribuciones de probabilidad en adelante . La distribución es la distribución de probabilidad de elegir los primeros bits con una probabilidad dada por y los bits restantes de manera uniforme y aleatoria. Tenemos así: ${\displaystyle \mu _{k,i}}$ ${\displaystyle {\overline {\mu _{k,i}}}}$ ${\displaystyle R_{k,i}}$ ${\displaystyle \mu _{k,i}}$ ${\displaystyle i}$ ${\displaystyle S_{k}}$ ${\displaystyle \mu _{k}}$ ${\displaystyle P(k)-i}$

${\displaystyle \mu _{k,i}(w_{1}\ldots w_{P(k)})=\left(\sum _{s\in S_{k},s_{1}\ldots s_{i}=w_{1}\ldots w_{i}}\mu _{k}(s)\right)\left({\frac {1}{2}}\right)^{P(k)-i}}$

${\displaystyle {\overline {\mu _{k,i}}}(w_{1}\ldots w_{P(k)})=\left(\sum _{s\in S_{k},s_{1}\ldots s_{i-1}(1-s_{i})=w_{1}\ldots w_{i}}\mu _{k}(s)\right)\left({\frac {1}{2}}\right)^{P(k)-i}}$

Por lo tanto, tenemos (un simple truco de cálculo lo muestra), por lo tanto, distribuciones y se pueden distinguir por . Sin pérdida de generalidad, podemos suponer que , con un polinomio. ${\displaystyle \mu _{k,i}={\frac {1}{2}}(\mu _{k,i+1}+{\overline {\mu _{k,i+1}}})}$ ${\displaystyle \mu _{k,i+1}}$ ${\displaystyle {\overline {\mu _{k,i+1}}}}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle p_{\mu _{k,i+1}}^{\mathcal {M}}-p_{\overline {\mu _{k,i+1}}}^{\mathcal {M}}\geq {\frac {1}{2}}+{\frac {1}{R(k)}}}$ ${\displaystyle R}$

Esto nos da una posible construcción de una máquina de Turing que resuelve la prueba del siguiente bit: al recibir los primeros bits de una secuencia, rellena esta entrada con una estimación de bits y luego con bits aleatorios, elegidos con probabilidad uniforme. Luego se ejecuta y genera si el resultado es y en caso contrario. ${\displaystyle i}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle l}$ ${\displaystyle P(k)-i-1}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle l}$ ${\displaystyle 1}$ ${\displaystyle 1-l}$

Referencias

1. Andrew Chi-Chih Yao . Teoría y aplicaciones de funciones-trampa. En Actas del 23º Simposio del IEEE sobre fundamentos de la informática, 1982.
2. Manuel Blum y Silvio Micali , Cómo generar secuencias criptográficamente fuertes de bits pseudoaleatorios, en SIAM J. COMPUT., vol. 13, núm. 4, noviembre de 1984