Prueba para el siguiente bit

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 9 de octubre de 2014; las comprobaciones requieren 9 ediciones .

La prueba para el siguiente bit ( ing. next-bit test ) es una prueba que sirve para probar la fuerza criptográfica de los generadores de números pseudoaleatorios . La prueba dice que no debería haber un algoritmo polinomial que, dados los primeros k bits de una secuencia aleatoria, pueda predecir k + 1 bits con probabilidad distinta de ½.

El problema de definir la aleatoriedad

En la teoría de la criptografía , un problema aparte es determinar qué tan aleatoria es una secuencia de números o bits generados por un generador. Por regla general, se utilizan varias pruebas estadísticas para este propósito, como las pruebas DIEHARD o las pruebas NIST . Andrew Yao demostró [1] en 1982 que un generador que pasa la "prueba del siguiente bit" pasará cualquier otra prueba de aleatoriedad estadística que se pueda realizar en tiempo polinomial.

Redacción

Un generador binario pasa la prueba para el siguiente bit si: para cualquier algoritmo probabilístico de tiempo polinomial A: -> {0,1} (Algoritmo que tiene como datos iniciales una secuencia de bits de longitud , y produce un bit en su salida), la siguiente es una desigualdad verdadera: $i$ ${\ estilo de visualización \ {0,1 \} ^ {i}}$ $i$

|P(A(s_{1}^{i-1})=s_{i})-1/2|<O(v(n)),

donde es la designación de una función decreciente más rápido que el polinomio inverso de grado n . ${\ estilo de visualización O (v (n))}$

Vale la pena señalar que la definición de una prueba para el siguiente bit no proporciona ningún algoritmo para realizar esta prueba.

Prueba extendida para el siguiente bit

Se considera que la secuencia binaria , recibida de la fuente S, ha pasado la prueba extendida para el ->siguiente bit si: para cualquier i y l: 1 < i, l < n y cualquier algoritmo probabilístico de tiempo polinomial A: ${\ estilo de visualización s_ {1}^ {n}}$ ${\ estilo de visualización \ {0,1 \} ^ {i-1}}$ ${\ estilo de visualización \ {0,1\}^ {l}}$

|P(A(s_{1}^{i-1})=s_{i}^{1-i+l})-(1/2)^{l}|<O(v(n ))

Se demuestra que la prueba extendida para el siguiente bit y la prueba para el siguiente bit son equivalentes. [2]

Pruebas de secuencias desequilibradas

Aunque la siguiente prueba de bit es un método universal para verificar la independencia de los bits de salida de una secuencia, solo es adecuada para secuencias no sesgadas, es decir, aquellas en las que la probabilidad de ocurrencia de uno es equivalente a la probabilidad de ocurrencia de cero .

Si la secuencia de salida obviamente debe tener algún sesgo , es decir , entonces esta prueba no es adecuada. $b$ $P(s_{i})=b$

Por lo tanto, para probar la independencia de los bits de salida de tales secuencias, se deben usar otras pruebas. En particular, se propuso una extensión de la prueba al siguiente bit: una prueba comparativa al siguiente bit [3] . La idea de la prueba es que inicialmente creemos que la distribución de la secuencia de salida está descrita por algún modelo matemático, y la prueba sirve para verificar el cumplimiento del generador con este modelo.

Benchmarking para el siguiente bit

Un generador binario pasa la prueba de comparación del siguiente bit de S contra el modelo M si: para cualquier i y cualquier algoritmo de tiempo polinomial probabilístico (es decir, un algoritmo que tiene una secuencia de bits de longitud i como entrada y salida de un bit), lo siguiente la desigualdad se cumple: : $A\dos puntos \{0,1\}^{i}\rightarrow \{0,1\}$

|P_{S}(A(s_{1}^{i-1})=s_{i})-P_{M}(A(s_{1}^{i-1})=s_{ i})|<O(v(n)),

donde es la probabilidad de que el algoritmo prediga el siguiente bit para el generador del modelo. $P_{M}(A(s_{1}^{i-1})=s_{i})$

Obviamente, dado un modelo M que representa una secuencia verdaderamente aleatoria, obtenemos , es decir, una prueba clásica para el siguiente bit. Dado el modelo con y , obtenemos el caso de prueba deseado para una secuencia no balanceada con un sesgo dado . $P_{M}(A(s_{1}^{i-1})=s_{i})=1/2)$ $P_{M}(A(s_{1}^{i-1})=1)=b$ $P_{M}(A(s_{1}^{i-1})=0)=1-b$ $b$

Implementaciones prácticas

Algoritmo de prueba Sadeghiyan-Mohajeri

Esta prueba aprovecha la estructura de árbol , que puede almacenar toda la información sobre las subsecuencias en la secuencia general.

El algoritmo para calcular secuencias de m bits se puede representar como un árbol binario con bordes ponderados. En este árbol, cada hoja en la profundidad l almacena información sobre cuántas veces se ha encontrado la secuencia de l bits dada. Dado que el árbol está ponderado, a cada uno de sus bordes se le asigna la proporción de la cantidad escrita en la hoja secundaria a la cantidad escrita en la principal. Para una secuencia aleatoria suficientemente grande, se supone que los números correspondientes a los bordes serán aproximadamente iguales a 1/2.

Pasos del algoritmo Sadeghian-Mahaery

Establecemos el nivel de error correspondiente a la distribución χ² con un grado de libertad y una suposición de error del 5%. $\alpha =\left(1+{\sqrt {(\chi ^{2})/n}}\right)/2$
Calculamos l = round( (n) - 1), n es la longitud de la secuencia en estudio. $registro_{2}$
Atribuimos los primeros bits al final de la secuencia y dividimos la secuencia en bloques superpuestos de longitud . ${\ estilo de visualización (l-1)}$ $yo$
Calculamos la frecuencia de las reuniones para todas las hojas de duración . $yo$
También formamos los niveles del árbol. Calculamos las probabilidades correspondientes para todos los bordes. $yo$ ${\ estilo de visualización (l-1)}$
Para cada hoja en el nivel (l-1), si el siguiente bit (0 o 1) ocurre con una probabilidad menor que α, el siguiente bit se predice de acuerdo con la frecuencia de esa ocurrencia. De lo contrario, la predicción es imposible.
Descartamos el bit más a la izquierda de la secuencia de l bits. Usando los bits restantes (l-1), vaya al paso 6 nuevamente y determine el siguiente bit. Repetimos esta operación el mayor tiempo posible. Después de obtener la imposibilidad de predecir el siguiente bit, contamos el número de bits predichos. Así obtenemos para cada secuencia de longitud (l-1) el número de bits siguientes predicho por el paso anterior.
Calcule un valor P igual a la relación entre los bits predichos y todos los intentos de predicción.

Establecemos el valor de r como la probabilidad de que el generador ideal genere una secuencia menos aleatoria que la de estudio. Por lo general, r se elige dentro de [0.001; 0,01]. Entonces, si el valor P es mayor que r, entonces la secuencia estudiada se considera aleatoria y viceversa en caso contrario.

La prueba de Sadeghyan-Mohaeri no proporciona un criterio claro y preciso para determinar la aleatoriedad de una secuencia. En cambio, los creadores del algoritmo asumen la capacidad de sacar algunas conclusiones sobre el comportamiento general de la secuencia. Cuando el algoritmo predice con éxito (l+1) bits, se considera que se ha producido un determinismo local.

Prueba de práctica para el siguiente latido (PNB)

El propósito de esta prueba es determinar las desviaciones en las estadísticas de ocurrencia del siguiente bit para una subsecuencia. Si existe tal desviación, la prueba intenta usarla para predecir el siguiente bit. Una secuencia se considera no aleatoria si contiene demasiadas subsecuencias cuyo último bit es predecible.

La prueba práctica muestra resultados más razonables en comparación con la prueba Sadeghyan-Mokhaeri original.

Pasos del algoritmo PNB

Establecimos el nivel de error correspondiente a la distribución con un grado de libertad y una suposición de error del 5%, de manera similar al algoritmo de Sadeghyan-Mokhaeri. $a={\frac {1+{\sqrt {X^{2}/n}}}{2}}$ ${\ estilo de visualización X^{2}}$
Calculamos l = round( (n) - 2), n es la longitud de la secuencia en estudio. $registro_{2}$
Mueva los primeros l bits al final de la secuencia.
Componemos un árbol similar al árbol en el algoritmo Sadeghyan-Mohaeri, en los nodos finales establecemos contadores correspondientes al número de ceros y unos en el siguiente bit.
“Escaneamos” la secuencia con una ventana de tamaño l bits. La posición inicial de la ventana son los primeros l bits. Con cada ciclo, avanzamos la ventana 1 bit hacia adelante y, según el valor del bit que sigue a la ventana, aumentamos el contador del nodo correspondiente a los valores de los bits en la ventana.
Para cada uno de los nodos, calculamos las proporciones y , donde y son los valores de los contadores para el nodo dado. Si una de estas proporciones excede α, entonces aumentamos el contador . ${\ estilo de visualización n_{0}/(n_{0}+n_{1})}$ ${\ estilo de visualización n_{1}/(n_{0}+n_{1})}$ $n_ {0}$ $n_{1}$ $Y_{o}bs$
Calcule el valor P = (1/2)* erfc (( - μ)/sqrt(2σ²) $Y_{o}bs$

Cabe señalar que no existe una teoría conocida [4] que permita calcular los valores exactos de μ y σ utilizados en el último paso del algoritmo. Por lo tanto, estos valores se calculan aproximadamente.

Véase también

Notas

↑ Andrew Chi-Chih Yao. Teoría y aplicaciones de funciones-trampa.
↑ A. Lavasani y T. Eghlidos. Prueba práctica del siguiente bit para evaluar secuencias pseudoaleatorias. Apéndice A
↑ AWSchrift, A. Shamir. Sobre la Universalidad de la Prueba del Siguiente Bit. 1998
↑ A. Lavasani y T. Eghlidos. Prueba práctica del siguiente bit para evaluar secuencias pseudoaleatorias. apéndice B

Literatura

Andrew Chi-Chih Yao. Teoría y aplicaciones de funciones-trampa.
A. Lavasani y T. Eghlidos. Prueba práctica del siguiente bit para evaluar la secuencia pseudoaleatoria
Paso Rafael. criptografía. Conferencias.