Prueba del siguiente bit

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 prueba del siguiente bit para cualquier posición.${\displaystyle i}$en la secuencia, si algún atacante que conoce el${\displaystyle i}$Los primeros bits (pero no la semilla) no pueden predecir el${\displaystyle (i+1)}$con una capacidad de cálculo razonable.

Dejar${\displaystyle P}$sea ​​un polinomio, y${\displaystyle S=\{S_{k}\}}$sea ​​una colección de conjuntos tal que${\displaystyle S_{k}}$contiene${\displaystyle P(k)}$Secuencias de -bits de longitud. Además, deje que${\displaystyle \mu _{k}}$sea ​​la distribución de probabilidad de las cadenas en${\displaystyle S_{k}}$.

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

La prueba del siguiente bit es un caso particular de la prueba de Yao para secuencias aleatorias, y superarla es, por lo tanto, una condición necesaria para superar la prueba de Yao . Sin embargo, Yao también ha demostrado que es una condición suficiente . ^{[ 1 ]}

Ahora lo demostramos en el caso de la máquina de Turing probabilística, ya que Adleman ya realizó el trabajo de reemplazar la aleatorización por la no uniformidad en su teorema . El caso de los circuitos booleanos no se puede derivar de este caso (ya que implica la resolución de problemas potencialmente indecidibles), pero la demostración del teorema de Adleman se puede adaptar fácilmente al caso de familias de circuitos booleanos no uniformes.

Dejar${\displaystyle {\mathcal {M}}}$ser un elemento distintivo para la versión probabilística de la prueba de Yao, es decir, una máquina de Turing probabilística, que se ejecuta en tiempo polinomial, de tal manera que existe un polinomial${\displaystyle Q}$de tal manera que para infinitos${\displaystyle k}$

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

Dejar${\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)}\}}$. Tenemos:${\displaystyle R_{k,0}=\{0,1\}^{P(k)}}$y${\displaystyle R_{k,P(k)}=S_{k}}$. Entonces, observamos que${\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)}}}$. Por lo tanto, al menos uno de los${\displaystyle |p_{k,R_{k,i+1}}^{\mathcal {M}}-p_{k,R_{k,i}}^{\mathcal {M}}|}$no debe ser menor que${\displaystyle {\frac {1}{Q(k)P(k)}}}$.

A continuación, consideramos las distribuciones de probabilidad.${\displaystyle \mu _{k,i}}$y${\displaystyle {\overline {\mu _{k,i}}}}$en${\displaystyle R_{k,i}}$. Distribución${\displaystyle \mu _{k,i}}$es la distribución de probabilidad de elegir el${\displaystyle i}$primeros fragmentos en${\displaystyle S_{k}}$con probabilidad dada por${\displaystyle \mu _{k}}$y el${\displaystyle P(k)-i}$Los bits restantes se distribuyen uniformemente al azar. Por lo tanto, tenemos:

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

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