Probabilistic estimation of the algebraic degree of cryptographic Boolean functions
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.
History
School
- Science
Department
- Computer Science
Publisher
Loughborough UniversityRights holder
© Percy ReyesPublication date
2023Notes
A Doctoral Thesis. Submitted in partial fulfilment of the requirements for the award of the degree of Doctor of Philosophy of Loughborough University.Language
- en
Supervisor(s)
Ana SalageanQualification name
- PhD
Qualification level
- Doctoral
This submission includes a signed certificate in addition to the thesis file(s)
- I have submitted a signed certificate