On the multi _ chi-square tests and their data complexity

Vardasbi, A.; Salmasizadeh, M.; Mohajeri, J.

doi:10.22042/isecure.2015.4.1.3

On the multi _ chi-square tests and their data complexity

Document Type : Research Article

Authors

A. Vardasbi

M. Salmasizadeh

J. Mohajeri

https://doi.org/10.22042/isecure.2015.4.1.3

Abstract

Chi-square tests are generally used for distinguishing purposes; however when they are combined to simultaneously test several independent variables, extra notation is required. In this study, the chi-square statistics in some previous works is revealed to be computed half of its real value. Therefore, the notion of Multi _ Chi-square tests is formulated to avoid possible future confusions. In order to show the application of Multi _ Chi square tests, two new tests are introduced and applied to reduce round Trivium as a special case. These tests are modifications of the ANF monomial test, and when applied to Trivium with the same number of rounds, the data complexity of them is roughly 2⁴ times smaller than that of former ANF monomial test. In a Multi _ Chi-square test the critical degrees of freedom is defined to be the minimum value of the degrees of freedom for which the test is successful at distinguishing the samples set from random. This study investigates the relation between this critical value and the chi-square statistic of a Multi _ Chi-square test. In the sequel, by exploiting this relation, a method to approximate the data complexity of a distinguishing Multi _ Chi-square test is introduced and shown to perform properly in the special case of reduced round Trivium.

Keywords

Multi _ Chi-square Test

Distinguishing Attacks

Critical Degrees of Freedom

Trivium

20.1001.1.20082045.2012.4.1.3.3

[1] Håkan Englund, Thomas Johansson, and Meltem Sönmez Turan. A Framework for Chosen IV Statistical Analysis of Stream Ciphers. In Proceedings of the cryptology 8^th international conference on Progress in cryptology, INDOCRYPT'07, pages 268-281, Berlin, Heidelberg, 2007. Springer- Verlag.

[2] Markku juhani O. Saarinen. Chosen-IV Statistical Attacks on Estream Stream Ciphers. In eSTREAM, ECRYPT Stream Cipher Project, Report 2006/013, pages 5-19, 2006.

[3] Eric Filiol. A New Statistical Testing for Symmetric Ciphers and Hash Functions. In Proceedings of the 4^th International Conference on Information and Communications Security, ICICS '02, pages 342-353, London, UK, UK, 2002. Springer-Verlag.

[4] K. Pearson. On The Criterion that a Given System of Deviations from the Probable in the Case of a Correlated System of Variables is Such that it Can be Reasonably Supposed to Have Arisen from Random Sampling. Philosophical Magazine Series, 5(50):157-175, 1900.

[5] M.G. Kendall, A. Stuart, J.K. Ord, and S.F. Arnold. Kendall's Advanced Theory of Statistics: Classical inference and relationship. Number v. 2 in Kendall's library of statistics. Arnold, 1999.

[6] Simon Fischer, Shahram Khazaei, and Willi Meier. Chosen IV Statistical Analysis for Key Recovery Attacks on Stream Ciphers. In Proceedings of the Cryptology in Africa 1^st international conference on Progress in cryptology, AFRICACRYPT'08, pages 236-245, Berlin, Heidelberg, 2008. Springer-Verlag.

[7] Itai Dinur and Adi Shamir. Cube Attacks on Tweakable Black Box Polynomials. In Proceedings of the 28^th Annual International Conference on Advances in Cryptology: the Theory and Applications of Cryptographic Techniques, EUROCRYPT'09, pages 278-299, Berlin, Heidelberg, 2009. Springer-Verlag.

[8] Christophe De Cannière. Trivium: A Stream Cipher Construction Inspired by Block Cipher Design Principles. In Proceedings of the 9^th international conference on Information Security, ISC'06, pages 171-186, Berlin, Heidelberg, 2006. Springer-Verlag.

[9] M. Vielhaber. Breaking One.Fivium by AIDA an Algebraic IV Differential Attack, 2007. IACR ePrint Archive, Report 2007/413. AVailable from http://eprint.iacr.org/2007/413.pdf.

[10] Jean-Philippe Aumasson, Itai Dinur, Willi Meier, and Adi Shamir. Cube Testers and Key Recovery Attacks on Reduced-Round MD6 and Trivium. In Fast Software Encryption, pages 1-22, Berlin, Heidelberg, 2009. Springer-Verlag.