On the minimum Hamming distance between vectorial Boolean and affine functions

Gábor P. Nagy · 2025

Read On the minimum Hamming distance between vectorial Boolean and affine functions by Gábor P. Nagy (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-03905.txt.

Introduction

Gabor Nagy studies how far code-like functions sit from the simplest linear ones in a 2025 paper. Such functions, which map bit strings to bit strings, guard data in ciphers. Their gap to the linear set ties to two key strength traits, yet the true gap is hard to work out in most cases.

A 2017 guess set a cap on that gap for all such functions. Nagy proves the cap for two classes of top-grade bent functions built from group-like tables. He also sharpens known bounds for two classes of single-term functions. For many famed strong functions in up to nine bits, he works out the exact gap.

Catalog record

CREATORGábor P. Nagy
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-03905

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the minimum Hamming distance between vectorial Boolean and affine functions Thanks: Support provided from the Program of Excellence TKP2021-NVA-02 at the Budapest University of Technology and Economics. Gábor P. Nagy Abstract . In this paper, we study the Hamming distance between vectorial Boolean functions and affine functions. This parameter is known to be related to the non-linearity and differential uniformity of vectorial functions, while the calculation of it is in general difficult. In 2017, Liu, Mesnager and Chen conjectured an upper bound for this metric. We prove this bound for two classes of vectorial bent functions, obtained from finite quasigroups in characteristic two, and we improve the known bounds for two classes of monomial functions of differential uniformity two or four. For many of the known APN functions of dimension at most nine, we compute the exact distance to affine functions. 2010 Mathematics Subject Classification 06E30,94A60,05B25 1. Introduction Vectorial Boolean functions f:\mathsf{GF}(2)^{n}\to\mathsf{GF}(2)^{m} , also called substitution boxes, play a central role in symmetric key block ciphers. Because they are the only non-linear components of the ciphers, they provide confusion. The study of the nonlinear properties of vectorial Boolean functions is fundamental for the evaluation of the resistance of the block cipher against the main attacks, such as the differential attack and the linear attack; see [ 15 , 1 ] . The two main metrics of these nonlinear properties are the differential uniformity \delta_{f} (the lower is the less linear), and the nonlinearity \mathrm{nl}(f) . The Walsh-Hadamard transform provides an effective tool for computation with nonlinearity \mathrm{nl}(f) . In this paper, we deal with a third metric, which is called by different names in the literature: vectorial nonlinearity \mathrm{NL}_{\boldmath{v}}(f) by the author of this paper [ 17 ] , distance to affine functions d_{H}(f,\mathcal{A}) by Carlet [ 7 ] , second type of nonlinearity \mathcal{N}_{\text{v}} by Liu, Mesnager, and Chen [ 14 ] . This metric should not be confused with the notion of r th-order nonlinearity of Boolean functions, which is the minimum Hamming distance of f from the set of all n -variable Boolean functions having an algebraic degree at most r , see [ 19 ] . In this paper, we use the terminology “distance to affine function”. For a map f:\mathsf{GF}(2)^{n}\to\mathsf{GF}(2)^{m} , we define d_{H}(f,\mathcal{A}) as the Hamming distance of f to the set \mathcal{A} of affine maps \mathsf{GF}(2)^{n}\to\mathsf{GF}(2)^{m} . The computation of d_{H}(f,\mathcal{A}) is generally difficult. In addition, it is difficult to give non-trivial lower and upper bounds for d_{H}(f,\mathcal{A}) . The distance to affine functions is linked to the nonlinearity by the inequality \displaystyle d_{H}(f,\mathcal{A})\geq\mathrm{nl}(f), that holds for all f:\mathsf{GF}(2)^{n}\to\mathsf{GF}(2)^{m} ; see [ 14 ] . For recent results on bounds involving nonlinearity and differential uniformity, see [ 9 , 25 ] . Using the concept of Sidon sets and t -thin sets, the lower bound (1) \displaystyle d_{H}(f,\mathcal{A})\geq 2^{n}-\sqrt{\delta_{f}}\cdot 2^{n/2}-\frac{1}{2} has been shown in [ 17 ] by the author of this paper, and independently by Ryabov [ 18 ] . Concerning upper bounds, we have the trivial inequality \displaystyle d_{H}(f,\mathcal{A})\leq 2^{n}-n-1. The function f:\mathsf{GF}(2)^{n}\to\mathsf{GF}(2)^{m} is called an (n,m) -bent function, if its nonlinearity achieves the the covering radius upper bound: \displaystyle\mathrm{nl}(f)=2^{n-1}-2^{n/2-1}. For the class of (n,m) -bent functions, Carlet, Ding and Yuan [ 8 ] proved (2) \displaystyle\left(1-\frac{1}{2^{m}}\right)\big(2^{n}-2^{n/2}\big)\leq d_{H}(f,\mathcal{A})\leq\left(1-\frac{1}{2^{m}}\right)\big(2^{n}+2^{n/2}\big). In 2017, Liu, Mesnager and Chen formulated a conjecture: Problem (Liu-Mesnager-Chen Conjecture [ 14 ] ) . For any map f:\mathsf{GF}(2)^{n}\to\mathsf{GF}(2)^{m} , (3) \displaystyle d_{H}(f,\mathcal{A})\leq\left(1-\frac{1}{2^{m}}\right)\big(2^{n}-2^{n/2}\big) holds. In particular, if n=m , then (4) \displaystyle d_{H}(f,\mathcal{A})\leq 2^{n}-2^{n/2}-1. The covering radius bound implies the conjecture for m=1 . For (n,m) -bent functions, the conjecture implies the exact value of the distance from affine functions: (5) \displaystyle d_{H}(f,\mathcal{A})=\left(1-\frac{1}{2^{m}}\right)\big(2^{n}-2^{n/2}\big). Theorem 1 . Let t\leq m be positive integers and (\mathsf{GF}(2^{m}),+,\star) be a left pre-quasifield. Let the maps \gamma,\tau,h:\mathsf{GF}(2^{m})\to\mathsf{GF}(2^{t}) and \sigma:\mathsf{GF}(2^{m})\to\mathsf{GF}(2^{m}) be such that \gamma is balanced, \tau is surjective linear, \sigma is invertible, and h is arbitrary. Define the (2m,t) -bent functions f_{1},f_{2} as \displaystyle f_{1}(x,y) \displaystyle=\gamma\left(\star\frac{x}{y}\right), \displaystyle f_{2}(x,y) \displaystyle=\tau\left(\sigma(y)\star{x}\right)+h(y). Then d_{H}(f_{1},\mathcal{A})=d_{H}(f_{2},\mathcal{A})=\left(1-\frac{1}{2^{t}}\right)\big(2^{2m}-2^{m}\big). Theorem 2 . Let n be a positive integer. (i) If n is even and h_{1}(x)=x^{2^{n}-2} , then \displaystyle 2^{n}-\sqrt{2}\cdot 2^{n/2}-\frac{3}{2}\leq d_{H}(h_{1},\mathcal{A})\leq 2^{n}-2^{n/2}-2. (ii) If n is divisible by 4 , d=2^{n/2-1}+1 , and h_{2}(x)=x^{d} , then \displaystyle 2^{n}-\sqrt{2}\cdot 2^{n/2}-\frac{1}{2}\leq d_{H}(h_{2},\mathcal{A})\leq 2^{n}-2^{n/2}-2. In particular, the Liu-Mesnager-Chen Conjecture holds for both functions h_{1}(x) , h_{2}(x) . Notice that h_{1}(x) is Nyberg’s Field Inverse Function, used in the AES cryptosystem with n=8 . In even dimension, the Field Inverse Function has differential uniformity 4 . The function h_{2}(x) is a monomial APN function of Gold type, and the exponent is d=2^{k}+1 , where k=n/2-1 . As n/2 is even, k is odd and \gcd(k,n)=\gcd(n/2-1,n)=1 . The APN property of h_{2}(x) follows. At the end of the paper, we will present new results for the minimum Hamming distance between affine and APN functions of dimension n=6,7,8,9 . 2. Preliminaries Let A,B be finite sets. The function f:A\to B is balanced, if the preimage f^{-1}(b) has size |A|/|B| for all b\in B . The Hamming distance d_{H}(f,g) between two functions f,g:A\to B is defined as the number of inputs at which they differ: d_{H}(f,g)=|\{a\in A:f(a)\neq g(a)\}|. We say that a function f is linear, if its definition domain is a vector space over \mathsf{GF}(2) , and the function is \mathsf{GF}(2) -linear. The sum of a linear function and a constant is called an affine function. The space of affine functions \mathsf{GF}(2)^{n}\to\mathsf{GF}(2)^{m} is denoted by \mathcal{A}_{n,m} , or simply \mathcal{A} . Let q be a prime power, and t a positive integer. For x,y\in\mathsf{GF}(q)^{t} , x\cdot y denotes the (non-degenerate) inner product x_{1}y_{1}+\cdots+x_{t}y_{t} . If we identify the \mathsf{GF}(q) -vector spaces \mathsf{GF}(q^{t}) and \mathsf{GF}(q)^{t} , then the inner product can be written as \mathrm{Tr}_{\mathsf{GF}(q^{t})/\mathsf{GF}(q)}(xy) . The map \mathrm{Tr}_{\mathsf{GF}(q^{t})/\mathsf{GF}(q)}(x)=x+x^{q}+\cdots+x^{q^{t-1}} is the trace map of the field extension \mathsf{GF}(q^{t})/\mathsf{GF}(q) . The nonlinearity of a Boolean function f:\mathsf{GF}(2)^{n}\to\mathsf{GF}(2) is defined as the minimum Hamming distance between f and all affine Boolean functions in n variables, denoted by d_{H}(f,\mathcal{A}) , where \mathcal{A} is the set of all affine functions on n variables. The nonlinearity of a Boolean function can be expressed as: \mathrm{nl}(f)=d_{H}(f,\mathcal{A})=2^{n-1}-\frac{1}{2}\max_{a\in\mathsf{GF}(2)^{n}}|W_{f}(a)|, where W_{f}(a) is the Walsh-Hadamard transform of f : W_{f}(a)=\sum_{x\in\mathsf{GF}(2)^{n}}(-1)^{f(x)+a\cdot x},\qquad a\in\mathsf{GF}(2)^{m}. Parseval’s relation \sum_{a\in\mathsf{GF}(2)^{n}}W_{f}^{2}(a)=2^{2n} implies \mathrm{nl}(f)\leq 2^{n-1}-2^{n/2-1} for every n -variable Boolean function f . This bound, tight for every even n , is called the covering radius bound. Functions achieving this bound are called n -variable bent functions. The Maiorana-McFarland class is the most important direct construction of bent functions. Let \pi be an arbitrary permutation on the set \mathsf{GF}(2)^{n/2} , and let h be an arbitrary Boolean function in n/2 variables, x,y\in\mathsf{GF}(2)^{n/2} . Then f(x,y)=x\cdot\pi(y)+h(y) is a bent function in n variables. Vectorial Boolean functions, also called (n,m) -functions, are functions from \mathsf{GF}(2)^{n}\to\mathsf{GF}(2)^{m} . If v\in\mathsf{GF}(2)^{m}\setminus\{0\} , then the Boolean function v\cdot f:\mathsf{GF}(2)^{n}\to\mathsf{GF}(2) , (v\cdot f)(x)=v\cdot f(x) is called a component Boolean function of f . The nonlinearity of f is the minimum distance between its component Boolean functions and affine Boolean functions: \mathrm{nl}(f)=\min_{\begin{subarray}{c}v\in\mathsf{GF}(2)^{m}\setminus\{0\}\\ \alpha\in\mathcal{A}_{n,1}\end{subarray}}d_{H}(v\cdot f,\alpha). By the covering radius bound, \mathrm{nl}(f)\leq 2^{n-1}-2^{n/2-1} . The functions achieving this bound are called (n,m) -bent functions, or vectorial bent functions, or bent vectorial functions. It is known that (n,m)

Read the complete text