Optimización del test LIL-débil para la evaluación de PRGN

Autores/as

  • Y. Matos Universidad de la Habana, Facultad de Matemática y Computación, Instituto de Criptografía, Cuba
  • C. M. Legón CUJAE, Facultad de Informática, Cuba
  • E. J. Madarro Universidad Central de las Villas, Cuba

Palabras clave:

Evaluación de PRGN, Test de aleatoriedad, Optimización del test LIL-débil

Resumen

La evaluación de aleatoriedad en generadores de números pseudoaleatorios (PRGN) es de gran importancia en criptograf ́ıa, existen numerosos tests de comprobación de aleatoriedad, muchos de ellos han sido diseñados basados en leyes importantes de aleatoriedad como el Teorema Central del L ́ımite y la Ley de los Grandes Números. Recientemente fue propuesto por Wang un novedoso test de tres variantes para la evaluación de generadores de números pseudoaleatorios, basado en la Ley del Logaritmo Iterado (LIL). Las probabilidades teóricas que deben calcularse para aplicar el test poseen una dependencia entre ellas, por lo cual se deben calcular secuencialmente. En este trabajo se propone una nueva expresióon, más simple que las expresiones dadas por Wang para el cálculo de estas probabilidades teóricas. La nueva expresión elimina la dependencia entre estas probabilidades y permite la optimización de las implementaciones del cálculo de las mismas utilizando los algoritmos secuencial y paralelos dados aqu ́ı, lo cual facilita la realización de experimentaciones más amplias.

Descargas

Los datos de descargas todavía no están disponibles.

Citas

E. Azmoodeh, G. Peccati y G. Poly. The law of iterated logarithm for subordinated Gaussian sequences: uniform Wasserstein bounds. ALEA, Lat. Am. Probab. Math. Stat. 13, 659-686, 2016.

A. Balsubramani, A. Ramdas. Sequential nonparametric testing with the law of the iterated logarithm. Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence. AUAI Press, p. 42-51, 2016.

E. Barker y J. Kelsey. NIST SP 800-90A: Recommendation for Random Number Generation Using Deterministic Random Bit Generators. NIST, 2012.

H. Demirhan y N. Bitirim. Statistical Testing of Cryptographic Randomness. Journal of Statisticians: Statistics and Actuarial Sciences IDIA 9, 1, 1-11, 2016.

Y. Dodis, C. Ganesh, A. Golovnev, A. Juels y T. Ristenpart. A Formal Treatment of Backdoored Pseudorandom Generators. Advances in Cryptology-EUROCRYPT 2015. 34th Annual Conference on the theory Applications of Cryptographic techniques, Sofia, Bulgaria, p. 102-128, 2015.

E. D. Erdmann. Empirical tests of binary keystreams. M.S. thesis, Department of Mathematics, Royal Holloway and Bedford New College, University of London, 1992.

W. Feller. Introduction to Probability Theory and Its Applications. vol. I, Wiely, Berlin, 1968.

K. G. Jamieson, M. Malloy, R. D. Nowak, S. Bubeck. lil’ucb: An optimal exploration algorithm for multiarmed bandits. COLT, vol. 35, p. 423-439, 2014.

A. Khintchine. Uber einen satz der wahrscheinlichkeitsrechnung. Fund. Math, 6: p. 9-20, 1924.

D. E. Knuth. The Art of Computer Programming, Seminumerical Algorithms. Vol. 2, 3 rd ed., Addison-Wesley, 1998.

P. L‘ecuyer. Software for uniform random number generation: Distinguishing the good and the bad. Proceedings of the Winter Simulation Conference. IEEE Press, p. 95-105, 2001.

P. L‘ecuyer. Random number generation. Handbook of Computational Statistics, J.E. Gentle, W. Haerdle, and Y. Mori, Eds. Springer-Verlag, Berlin, Germany. p. 35-70. Chapter II.2, 2004.

P. L‘ecuyer y R. Simard. Beware of linear congruential generators with multipliers of the form a = ±2 q ±2 r . ACM Trans. Math. Soft. 25, 3, p. 367-374, 1999.

P. L‘ecuyer y R. Simard. On the performance of birthday spacings tests for certain families of random number generators. Mathem. Comput. Simul. 55, p. 1-3, p. 131137, 2001.

P. L‘ecuyer, R. Simard y S. Wegenkittl. Sparse serial tests of uniformity for random number generators. SIAM J. Scient. Comput. 24, 2, p. 652-668, 2002.

P. L‘ecuyer y Richard Simard. A C Library for Empirical Testing of Random Number Generators. ACM Trans. Math. Softw. 33, 4, Article 22, 2007.

P. L‘ecuyer y R. Touzin. Fast combined multiple recursive generators with multipliers of the form a = ±2 q ±2 r . Proceedings of the Winter Simulation Conference. Fishwick, Eds. IEEE Press, p. 683-689, 2000.

P. Li, X. Yi, X. Liu, Yuncai Wang y Yongee Wang. Brownian motion properties of optoelectronic random bit generators based on laser chaos. OPTICS EXPRESS, Vol. 24, No. 14, 2016.

G. Marsaglia. A current view of random number generators. Computer Science and Statistics, Sixteenth Symposium on the Interface. Elsevier Science Publishers, North-Holland, Amsterdam, The Netherlands. p. 3-10, 1985.

G. Marsaglia. DIEHARD: A battery of tests of randomness. http://stat.fsu.edu/ geo/diehard.html, 1996.

G. Marsaglia y W.Tsang. Some difficult-to-pass tests of randomness. J. Statist. Soft. 7, 3, p. 1-9, 2002.

G. Marsaglia y A. Zaman. Monkey tests for random number generators. Comput. Math. Applic. 26, 9, p. 1-10, 1993.

M. Mascagni y A. Srinivasan. Algorithm 806: SPRNG: A scalable library for pseudorandom number generation. ACM Trans. Mathem. Soft. 26, p. 436-461, 2000.

K. Miyabe, A. Takemura. The law of the iterated logarithm in game-theoretic probability with quadratic and stronger hedges. Stochastic Process. Appl., 123(8), p. 3132-3152, 2013.

A. L. Rukhin. Testing randomness: A suite of statistical procedures. Theo. Probab. Applic. 45, 1, p. 111-132, 2001.

A. L. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel,D. Banks, A. Heckert, J. Dray y S. Vo. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. NIST SP 800-22, 2010.

T.Sasai, K.Miyabe, A. Takemura,. A game-theoretic proof of Erdos-Feller-Kolmogorov-Petrowsky law of the iterated logarithm for fair-coin tossing arXiv:1408.1790v2,[math.PR], 2014.

D. Shumow y N. Ferguson. On the possibility of a back door in the NIST SP800-90 Dual Ec Prng. Proc. Crypto’07, 2007.

Y. Song, G. Fellouris. Sequential multiple testing with generalized error control: an asymptotic optimality theory. arXiv:1608.07014v1 [math.ST], 2016.

Y. Song, G. Fellouris. Asymptotically optimal, sequential, multiple testing procedures with prior information on the number of signals. Electronic Journal of Statistics, ISSN: 1935-7524, Vol.11, p. 338-363, 2017.

I. Vattulainen, T. Ala-Nissila y K. Kankaala. Physical models as tests of randomness. Physic. Rev. E 52, 3, p. 3205-3213, 1995.

U. V. Vazirani y V. V. Vazirani. Trapdoor pseudo-random number generators, with applications to protocol design. FOCS. vol. 83, p. 23-30, 1983.

Y. Wang. On the Design of LIL Test for (Pseudo) Random Generators and Some Experimental Result. arXiv:1401.3307v1 [cs.CR], 2014.

Y. Wang y T. Nicol. On statistical distance based testing of pseudo random sequences and experiments with PHP and Debian Open SSL. Elsevier, Computers and Security, 53, p. 44-64, 2015.

Y. Wang. On Stochastic Security of Pseudorandom Sequences. http://webpages.uncc.edu/yonwang/papers/lilprfV2.pdf, 2014.

Y. Wang. Resource bounded randomness and computational complexity. Theoret. Comput. Sci., 237: p. 3355, 2000.

F. Yang, A. Ramdas, K. Jamieson, M. Wainwright. A framework for Multi-A(rmed)/B(andit) testing with online FDR control. arXiv:1706.05378v1 [stat.ML], 2017.

Descargas

Publicado

2018-06-01

Cómo citar

[1]
Matos, Y. et al. 2018. Optimización del test LIL-débil para la evaluación de PRGN. Ciencias matemáticas. 32, 1 (jun. 2018), 61–69.

Número

Vol. 32 Núm. 1: Junio, 2018

Sección

Artículo Original

Licencia

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.

Esta licencia permite copiar y redistribuir el material en cualquier medio o formato bajo los siguientes términos: se debe dar crédito de manera adecuada, no se puede hacer uso del material con propósitos comerciales, y si remezcla, transforma o crea a partir del material, no podrá distribuir el material modificado. Bajo la licencia mencionada, los autores mantienen los derechos de autor de su trabajo.