Nuevas Técnicas Computacionales para la estimación de la independencia de los tests de aleatoriedad

Abstract

La información mutua es una cantidad que mide la dependencia entre dos variables aleatorias. En particular, mide cuánta información, en promedio, proporciona una variable aleatoria a otra. En el artículo “Measuring Independence between Statistical Randomness Tests by Mutual Information” [KALPMC+20] de Jorge Augusto Karell-Albo, Carlos Miguel Legón-Pérez, Evaristo José Madarro-Capó, Omar Rojas y Guillermo Sosa-Gómez, se propuso la información mutua para medir la dependencia entre pruebas de aleatoriedad. Esta nueva herramienta puede ser útil para futuros avances en criptografía: no solo tendríamos otra forma de ver las posibles dependencias entre pruebas, además de la conocida correlación de Pearson, sino que también puede ayudarnos a ver otras dependencias que esta última no era capaz de detectar, ya que la correlación de Pearson solo detecta dependencias lineales (una restricción que no afecta la información mutua). Para empezar, replicaremos los resultados del artículo, que utiliza información mutua para buscar dependencias en la batería NIST, para verificar que nuestras implementaciones del cálculo de información mutua y la posterior prueba de permutación son correctas. Luego, ampliaremos los análisis a otras baterías de tests conocidas, como ENT, FIPS 140-2 o DieHarder, para detectar sus dependencias y comprobar si la información mutua es una buena medida de independencia.

Mutual information is a quantity that measures the dependence between two random variables. Particularly, it measures how much information, on average, one random variable provides to another. In the article “Measuring Independence between Statistical Randomness Tests by Mutual Information”[KALPMC+20] by Jorge Augusto Karell-Albo, Carlos Miguel Leg´on-P´erez, Evaristo Jos´e Madarro-Cap´o, Omar Rojas, and Guillermo Sosa-G´omez, this quantity is proposed to measure the dependence between randomness tests. This new tool can be helpful for future advances in cryptography: not only would we have another way of seeing possible dependencies between tests, apart from the well-known Pearson correlation, but it can also help us to see other dependencies that the latter was not able to detect, since the correlation Pearson’s only detects linear dependencies (a constraint that does not affect mutual information). To begin with, we will replicate the results of the article, which uses mutual information to look for dependencies in the National Institute of Standards and Technology (NIST) battery, to verify that our implementations of the mutual information calculation and the permutation test are correct. Then, we will extend the analyses to other known test batteries, such as ENT, Federal Information Processing Standards (FIPS) 140-2, or DieHarder, to detect their dependencies and to test the mutual information as an independence measure.