Sălăgean-Stănică2022_Article_ImprovingBoundsOnProbabilistic.pdf (522.42 kB)
Download file

Improving bounds on probabilistic affine tests to estimate the nonlinearity of Boolean functions

Download (522.42 kB)
journal contribution
posted on 28.01.2022, 10:07 authored by Ana SalageanAna Salagean, Pantelimon Stanica
In 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 Communications

Volume

14

Issue

2

Pages

459 - 481

Publisher

Springer

Version

VoR (Version of Record)

Rights holder

© the Authors

Publisher 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

04/08/2021

Publication date

2021-11-19

Copyright date

2021

ISSN

1936-2447

eISSN

1936-2455

Language

en

Depositor

Deposit date: 28 January 2022