• PDF / 268,115 Bytes
• 17 Pages / 595.276 x 841.89 pts (A4) Page_size
• 86 Downloads / 218 Views

DOWNLOAD

REPORT

---

Analyzing Boolean Functions via Solving Parametric Polynomial Systems∗ HUANG Zhenyu · SUN Yao · LIN Dongdai

DOI: 10.1007/s11424-020-9209-6 Received: 18 July 2019 c The Editorial Office of JSSC & Springer-Verlag GmbH Germany 2020 Abstract In this paper, a new method to analyze Boolean functions is proposed. By this method, one can analyze the balancedness, the nonlinearity, and the input-output correlation of vectorial Boolean functions. The basic idea of this method is to compute the refined covers of some parametric Boolean polynomial systems which are equivalent to these problems. By a refined cover, the parameter space is divided into several disjoint components, and on each component, the parametric Boolean polynomial system has a fixed number of solutions. An efficient algorithm based on the characteristic set method to compute refined covers of parametric Boolean polynomial systems is presented. The experimental results about some instances generated from cryptanalysis show that this new method is efficient and can solve some instances which can not be solved in reasonable time by other methods. Keywords Boolean functions, characteristic set method, correlation, nonlinearity, parametric Boolean polynomial systems.

1

Introduction

Boolean functions play a critical role in cryptography, especially in the design of symmetric key ciphers. For example, S-boxs in block ciphers and augmented functions of stream ciphers all can be represented by Boolean functions[1, 2] . The balancedness, nonlinearity, and correlation are basic properties of Boolean functions, and are widely investigated in cryptography research[3–5] . These properties are highly relevant to the linear attacks, correlation attacks, algebraic attacks, and distinguish attacks of ciphers. To the best of the authors’ knowledge, the main approach to analyze these properties of a Boolean function is to compute its Hadamard transform, and this can be done by the fast Hadamard transform, whose complexity is Θ (n2n ) for a Boolean function with n variables[1] . It is easy to see that when the number of variables HUANG Zhenyu · SUN Yao · LIN Dongdai SKLOIS, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China. Email: [email protected]; [email protected]; [email protected]. ∗ This research was in part supported by the National Natural Science Foundation of China under Grant Nos. 61977060 and 61877058.  This paper was recommended for publication by Editor LI Hongbo.

2

HUANG ZHENYU · SUN YAO · LIN DONGDAI

exceeds 60, the fast Hadamard transform cannot work in reasonable time by current computer capability. In this paper, we will introduce a new method to analyze these properties of Boolean functions. We focus on the multi-output Boolean functions, which are also called the vectorial Boolean functions. Obviously, Boolean functions in the common sense are vectorial Boolean functions with one bit output. A vectorial Boolean function F : Fn2 → Fm 2 can be represented by its algebraic normal form (f1 (X), f2 (X), · · · , fm (X)), wh