Gowers U2 norm as a measure of nonlinearity for Boolean functions and their generalizations

Thumbnail Image
Files
2019AMC_NewGowers.pdf (367.76 KB)
Authors
Gangopadhyay, Sugata
Riera, Constanza
Stănică, Pantelimon
Subjects
Gowers norms
Boolean functions
bent functions
Z-bent functions
Advisors
Date of Issue
2020
Date
Publisher
American Institute of Mathematical Sciences
Language
Abstract
In this paper, we investigate the Gowers U2 norm for generalized Boolean func- tions, and Z-bent functions. The Gowers U2 norm of a function is a measure of its resistance to affine approximation. Although nonlinearity serves the same purpose for the classical Boolean functions, it does not extend easily to generalized Boolean functions. We first pro- vide a framework for employing the Gowers U2 norm in the context of generalized Boolean functions with cryptographic significance, in particular, we give a recurrence rule for the Gowers U2 norms, and an evaluation of the Gowers U2 norm of functions that are affine over spreads. We also give an introduction to Z-bent functions, as proposed by Dobbertin and Leander [8], to provide a recursive framework to study bent functions. In the second part of the paper, we concentrate on Z-bent functions and their U2 norms. As a consequence of one of our results, we give an alternate proof to a known theorem of Dobbertin and Leander, and also find necessary and sufficient conditions for a function obtained by gluing Z-bent functions to be bent, in terms of the Gowers U2 norms of its components.
Type
Article
Description
URI
https://hdl.handle.net/10945/64448
Series/Report No
Department
Applied Mathematics
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Gangopadhyay, Sugata, Constanza Riera, and Pantelimon Stănică. "Gowers U2 norm as a measure of nonlinearity for Boolean functions and their generalizations." (2020).
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Collections
Publications