Predicting the number of different dimensional cubes: theoretically evaluate the secure bound of cryptographic primitives against the balance testers

摘要

The cube tester is a powerful tool to detect non-randomness of cryptographic primitives. The balance tester is a kind of powerful cube tester that has been applied to various cryptographic primitives. However, most existing results of the balance tester are acquired experimentally using small cubes of dimension no more than 50. To understand the mechanic of the balance tester, it is necessary to predict the number of higher-dimensional cubes. In this paper, we firstly draw links between the number of cubes and the resistance against the balance tester. Secondly, we theoretically prove that there are lower and upper bounds for the number of each dimensional cubes using a probabilistic model. Based on our analysis, we propose our main algorithms that can draw the lower and upper bounds for the number of different dimensional cubes utilising some easily acquired statistics. We apply our main algorithms to some famous stream ciphers namely Trivium, Grain-128, Grain-128a and Grain-v1. The results are in high accordance with our theories and expectations. Our work provides a better understanding of the balance tester. We expect that our main algorithms will equip the cryptologists with useful information when evaluating the secure margin of newly designed ciphers.