2023/06/21 by Ana Sălăgean, Salagean, Ana, Percy Reyes-Paredes +1
Computer Science · #11T06 #94A60 #Coding theory and cryptography #Cryptographic Implementations and Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2306.12196
openalex publication_date 2023/06/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 might not be feasible to compute its degree. Instead, one can try to estimate the degree using probabilistic tests. We propose a probabilistic test for deciding whether the algebraic degree of a Boolean function f is below a certain value k. The test involves picking an affine space of dimension k and testing whether the values on f on that space sum up to zero. If deg(f)