Estimating the nonlinearity of Boolean functions using probabilistic linearity tests

In this paper we concentrate on estimating the nonlinearity of Boolean functions, by probabilistic methods, when it is not feasible to compute the full Walsh transform. Firstly, we improve upon the bounds on the probabilities of failure of existing affinity tests. Secondly, we provide probabilistic...

Full description

Saved in:
Bibliographic Details
Main Authors: Ana Salagean, Pantelimon Stanica
Format: Default Conference proceeding
Published: 2020
Subjects:
probabilistic testing
Walsh transform
nonlinearity
Online Access:https://hdl.handle.net/2134/14453181.v1
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we concentrate on estimating the nonlinearity of Boolean functions, by probabilistic methods, when it is not feasible to compute the full Walsh transform. Firstly, we improve upon the bounds on the probabilities of failure of existing affinity tests. Secondly, we provide probabilistic tests for estimating nonlinearity based upon either affinity tests or linearity tests (such as the BLR test) and analyze the accuracy of the estimation.

Similar Items