Probabilistic estimation of the algebraic degree of cryptographic Boolean functions

• Main Author: Percy Reyes-Paredes
• Format: Dissertation
• Language: English
• Subjects: Algebraic Degree; Algebraic normal form; Boolean Functions; Finite Fields; Fourier Transform; Moebius Transform; Other information and computing sciences not elsewhere classified; Probabilistic Estimation
• DOI: 10.26174/thesis.lboro.24534487.v1

We propose a probabilistic test, called the deg(f) < k test, for deciding whether the algebraic degree of a cryptographic Boolean function f (given as a black box) is below a certain value k. When f is indeed of degree below k, then f always passes the deg(f) < k test, otherwise it fails each run of the test with a probability dt_k(f). The deg(f) < k test has a good accuracy when the probability dt_k(f) of failing the test is not too small. Ana Salagean initiated the study of the probability dt_k(f) of failing the deg(f) < k test for the case when f is of degree k, and she proved in Theorem 3.32 that there is no function with very low probability dt_k(f), which is in the interval (0.288788, 0.5], and therefore a small number of runs of the test is sufficient to give, with very high probability, the correct answer. We study the probability dt_k(f) when all monomials of f have no variables in common, and prove that dtk_{k-1}(f) >= dt_k(f) holds for this case. Also, we prove that monomials of degree less than k do not alter value of dtk(f). We then study the probability dt_{k-1}(f) of failing the deg(f) < k-1 test when f is of degree k, and we prove that dtk_{k-1}(f) >= dtk(f) holds for particular cases, such as for polynomial classes of one monomial and for all polynomials of degree 2, as well as for the general case. We firstly conjectured these results based on the exact dt_3(f) and dt_4(f) values that we computed for all polynomials of degree 4 in 7 variables, by using the 68431 representatives of equivalence classes listed by Langevin in [33]. Interestingly, dtk_{k-1}(f) >= dtk(f) means that the deg(f) < k-1 test works even more effectively than the deg(f) < k test and that the bounds (0.288788, 0.5] also hold for dtk_{k-1}(f) when f is of degree k. We also computed the exact dt_k(f) values for all polynomials of degree k = 1, 2, 3, 4 in 8 variables, by using the representatives of equivalence classes listed by Hou in [17] and by Langevin and Leander listed in [35]. We run the deg(f) < k test experimentally on various stream ciphers, including Trivium, Grain-128a, and SNOW-V. The resulting probability values mostly fall within the range of (0.47, 0.52). Additionally, we used these tests to estimate the degree for these ciphers at different numbers of rounds and different settings for key bits and IV bits.