WE1.R1.2

An Answer to an Open Problem on Balanced Boolean Functions with the Maximum Possible Walsh Supports

Yueying Lou, Qichun Wang, Nanjing Normal University, China

Session:
Symmetric Cryptography

Track:
5: Cryptography

Location:
Ballroom II & III

Presentation Time:
Wed, 10 Jul, 10:10 - 10:30

Session Chair:
Lukas Koelsch,
Abstract
Boolean functions play an important role in symmetric ciphers. Various cryptographic criteria such as nonlinearity, balancedness, correlation immunity and transparency order are closely related to the Walsh support of a Boolean function. %Walsh transform serves as an important mathematical tool for studying cryptographic criteria of Boolean functions. However, we did not know more about the possible structure of Walsh supports of Boolean functions until Carlet and Mesnager conducted an in-depth study of Walsh supports for Boolean functions in 2005, proposing a class of $n$-variable balanced Boolean functions with Walsh support $\mathbb{F}_{2}^{n} \backslash \{0\}$, for $n\ge 10$. For $n\le 6$, it can be verified using the computer that there is no Boolean function with the Walsh Support $\mathbb{F}_{2}^{n} \backslash \{0\}$. Nevertheless, for $n=7,8,9$, whether there is an $n$-variable Boolean function whose Walsh support is $\mathbb{F}_{2}^{n} \backslash \{0\}$ has been an open problem for many years. In this paper, we aim to solve this problem. For $n=7$, based on the technique of concatenation, we obtain a 7-variable function with Walsh support $\mathbb{F}_{2}^{n} \backslash \{a\}$ through finding two 6-variable Boolean functions whose Walsh spectra are equal or negative at only one point. Then, using the linear transformation, we naturally get a 7-variable balanced Boolean function with Walsh support $\mathbb{F}_{2}^{n} \backslash \{0\}$. For $n=8,9$, we construct mathematically a balanced Boolean function whose Walsh support is $\mathbb{F}_{2}^{n} \backslash \{0\}$ respectively. Therefore, we solve the above open problem completely.
Resources