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 en cualquier posición de la secuencia, si algún atacante que conoce los primeros bits (pero no la semilla) no puede predecir el st con un poder computacional razonable.${\displaystyle i}$${\displaystyle i}$${\displaystyle (i+1)}$

Declaración (es) precisa (s)

Sea un polinomio y una colección de conjuntos tales que contengan secuencias de -bit 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 formas 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 entradas exactas . 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 fuerte (ver el teorema de Adleman ). Sea una máquina de Turing probabilística, trabajando en tiempo polinomial. Sea la probabilidad que predice correctamente el bit st, 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)}}}$

Integridad para 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, aprobarla es una condición necesaria para aprobar la prueba de Yao . Sin embargo, también se ha demostrado una condición suficiente por Yao . ^[1]

Lo demostramos ahora en el caso de la máquina probabilística de Turing, ya que Adleman ya ha realizado el trabajo de reemplazar la aleatorización con 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 de Turing probabilística, que se ejecuta en tiempo polinomial, de modo que hay un polinomio tal que para infinitos${\displaystyle {\mathcal {M}}}$${\displaystyle Q}$${\displaystyle k}$

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

Deja . Tenemos: y . Entonces, lo notamos . Por lo tanto, al menos uno de los 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 distribuciones de probabilidad y así sucesivamente . La distribución es la distribución de probabilidad de elegir los primeros bits con probabilidad dada por , y los bits restantes uniformemente al azar. 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 muestra esto), por lo tanto, distribuciones y se pueden distinguir por . Sin pérdida de generalidad, podemos asumir eso , 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 suposición de bits y luego bits aleatorios, elegidos con probabilidad uniforme. Luego se ejecuta y genera si el resultado es , y de lo 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 las funciones de trampilla . En Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982.
2. Manuel Blum y Silvio Micali , Cómo generar secuencias criptográficamente fuertes de bits pseudoaleatorios, en SIAM J. COMPUT., Vol. 13, No. 4, noviembre de 1984