Probabilistic estimation of the algebraic degree of Boolean functions

The algebraic degree is an important parameter of Boolean functions used in cryptography. When a function in a large number of variables is not given explicitly in algebraic normal form, it is usually not feasible to compute its degree, so we need to estimate it. We propose a probabilistic test for...

Full description

Saved in:
Bibliographic Details
Main Authors: Ana Salagean, Percy Reyes-Paredes
Format: Article
Language:English
Subjects:
Algebraic degree
Algebraic thickness
Applied mathematics
Moebius transform
Numerical and computational mathematics
Probabilistic testing
Pure mathematics
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The algebraic degree is an important parameter of Boolean functions used in cryptography. When a function in a large number of variables is not given explicitly in algebraic normal form, it is usually not feasible to compute its degree, so we need to estimate it. We propose a probabilistic test for deciding whether the algebraic degree of a Boolean function f is below a certain value k. If the degree is indeed below k, then f will always pass the test, otherwise f will fail each instance of the test with a probability dtk(f), which is closely related to the average number of monomials of degree k of the polynomials which are affine equivalent to f. The test has a good accuracy only if this probability dtk(f) of failing the test is not too small. We initiate the study of dtk(f) by showing that in the particular case when the degree of f is actually equal to k, the probability will be in the interval (0.288788, 0.5], and therefore a small number of runs of the test will be sufficient to give, with very high probability, the correct answer. Exact values of dtk(f) for all the polynomials in 8 variables were computed using the representatives listed by Hou and by Langevin and Leander.