The ISC International Journal of Information Security

Current Issue

By Issue

By Author

By Subject

Author Index

Keyword Index

About Journal

Aims and Scope

Editorial Board

Editorial Staff

Publication Ethics and Malpractice Statement

Indexing and Abstracting

Related Links

FAQ

Peer Review Process

News

Sponsors

Journal Metrics

Reviewers

Review Guide in Publons

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

Document Type : Research Article

Authors

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 24 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

Optional file type 1
[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 8th 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 4th 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 1st 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 28th 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 9th 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.
 
The ISC International Journal of Information Security
Volume 4, Issue 1 - Serial Number 1
20
January 2012
Pages 15-24
Files
Share
How to cite
Statistics