Sălăgean-Stănică2022_Article_ImprovingBoundsOnProbabilistic.pdf (522.42 kB)
Download fileImproving bounds on probabilistic affine tests to estimate the nonlinearity of Boolean functions
journal contribution
posted on 2022-01-28, 10:07 authored by Ana SalageanAna Salagean, Pantelimon StanicaIn this paper we want to estimate the nonlinearity of Boolean functions, by probabilistic methods, when it is computationally very expensive, or perhaps not feasible to compute the full Walsh transform (which is the case for almost all functions in a larger number of variables, say more than 30). Firstly, we significantly improve upon the bounds of Zhang and Zheng (1999) on the probabilities of failure of affinity tests based on nonhomomorphicity, in particular, we prove a new lower bound that we have previously conjectured. This new lower bound generalizes the one of Bellare et al. (IEEE Trans. Inf. Theory 42(6), 1781–1795 1996) to nonhomomorphicity tests of arbitrary order. Secondly, we prove bounds on the probability of failure of a proposed affinity test that uses the BLR linearity test. All these bounds are expressed in terms of the function’s nonlinearity, and we exploit that to provide probabilistic methods for estimating the nonlinearity based upon these affinity tests. We analyze our estimates and conclude that they have reasonably good accuracy, particularly so when the nonlinearity is low.
History
School
- Science
Department
- Computer Science
Published in
Cryptography and CommunicationsVolume
14Issue
2Pages
459 - 481Publisher
SpringerVersion
- VoR (Version of Record)
Rights holder
© the AuthorsPublisher statement
This is an Open Access Article. It is published by Springer under the Creative Commons Attribution 4.0 Unported Licence (CC BY). Full details of this licence are available at: http://creativecommons.org/licenses/by/4.0/Acceptance date
2021-08-04Publication date
2021-11-19Copyright date
2021ISSN
1936-2447eISSN
1936-2455Publisher version
Language
- en