Bent Functions (eBook)

Results and Applications to Cryptography

Natalia Tokareva (Autor)

eBook Download: PDF | EPUB

2015 | 1. Auflage
220 Seiten
Elsevier Science (Verlag)
978-0-12-802555-0 (ISBN)

Infos

Bent Functions: Results and Applications to Cryptography offers a unique survey of the objects of discrete mathematics known as Boolean bent functions. As these maximal, nonlinear Boolean functions and their generalizations have many theoretical and practical applications in combinatorics, coding theory, and cryptography, the text provides a detailed survey of their main results, presenting a systematic overview of their generalizations and applications, and considering open problems in classification and systematization of bent functions.

The text is appropriate for novices and advanced researchers, discussing proofs of several results, including the automorphism group of bent functions, the lower bound for the number of bent functions, and more.

• Provides a detailed survey of bent functions and their main results, presenting a systematic overview of their generalizations and applications
• Presents a systematic and detailed survey of hundreds of results in the area of highly nonlinear Boolean functions in cryptography
• Appropriate coverage for students from advanced specialists in cryptography, mathematics, and creators of ciphers

Dr. Natalia Tokareva is a senior researcher at the Laboratory of Discrete Analysis in the Sobolev Institute of Mathematics and she teaches courses in cryptology in the Department of Mathematics and Mechanics at Novosibirsk State University. She has studied bent functions and their applications for several years, publishing one monograph (in Russian) and more than 12 articles. She has been a participant of many international conferences and seminars and presentations in the area of bent functions, particularly with applications in cryptography. Her research interests include Boolean functions in cryptography, bent functions, block and stream ciphers, cryptanalysis, coding theory, combinatorics, and algebra. She is chief of the seminar 'Cryptography and Cryptanalysis' at the Sobolev Institute of Mathematics and she supervises BS, MS, and PhD students in discrete mathematics and cryptology.

Textauszug

Chapter 1

Boolean Functions

Abstract

In this chapter, we start with basic definitions related to Boolean functions. We consider the algebraic normal form of a Boolean function and the representation of a Boolean function over the Boolean cube. Extended affinely equivalent Boolean functions are defined as is the Walsh-Hadamard transform of a Boolean function. The finite field over 2 and its automorphisms are considered. It is shown how to associate Boolean functions in n variables with functions over the field 2n. We discuss polynomial representations of Boolean and vectorial Boolean functions. Representations of a Boolean function in the trace form and in the reduced trace form are given. Some details on the degree of a Boolean function in the trace form and on monomial functions are presented. The notions introduced in this chapter will be useful throughout the book.

Keywords

Boolean function

Vectorial function

Algebraic normal form

Boolean cube

Hamming distance

Extended affine equivalence

Walsh-Hadamard transform

Finite field

Polynomial form

Trace form

Monomial function

Introduction

In this chapter, we start with basic definitions related to Boolean functions. We consider the algebraic normal form of a Boolean function and the representation of a Boolean function over the Boolean cube. Extended affinely equivalent Boolean functions are defined as is the Walsh-Hadamard transform of a Boolean function. The finite field over 2 and its automorphisms are considered. It is shown how to associate Boolean functions in n variables with functions over the field 2n. We discuss polynomial representations of Boolean and vectorial Boolean functions. Representations of a Boolean function in the trace form and in the reduced trace form are given. Some details on the degree of a Boolean function in the trace form and on monomial functions are presented. The notions introduced in this chapter will be useful throughout the book.

1.1 Definitions

Let 2n denote the n-dimensional vector space over the prime field 2. Let x = (x1,…,xn) be a vector over 2 of length n.

A Boolean function in nvariables is an arbitrary function from 2n to 2. It is called Boolean in honor of the British mathematician and philosopher George Boole (1815-1864).

Every Boolean function can be defined by its truth table:

x1…xn

f(x1,…,xn)

0 …0

*

1 …1

*

where in the first column there are all possible vectors of 2n and in the second column there are concrete values of a Boolean function taken on these vectors (denoted here by *). We suppose that the arguments of a function (i.e., vectors of length n) follow in lexicographical order. For example, if n = 3, the order is (000),(001),(010), (011),(100), (101), (110),(111).

For instance, the following are Boolean functions:

:F22→F2 such that g(00) = g(11) = 1, g(01) = g(10) = 0;

:F23→F2 such that h(x) = 1 if and only if x has two nonzero coordinates.

Their truth tables are as follows:

x1x2

g(x1,x2)

00

1

01

0

10

0

11

1

,

x1x2x3

h(x1,x2,x3)

000

0

001

0

010

0

011

1

100

0

101

1

110

1

111

0

It is easy to count the number of Boolean functions. There are 2n of them: to construct a function, one chooses 2n values (0 or 1) for f(x) when x runs through 2n.

Every Boolean function in n variables can be uniquely determined by its vector of values of length 2n. This is the transposed second column of its truth table.

In our examples, (1001) and (00010110) are vectors of values for g and h, respectively.

A vectorial Boolean function F in n variables is a function from 2n to 2m, where m is an integer. It is also called an (n,m)-function. In what follows in this book, we consider m = n unless otherwise stated. For vectorial Boolean functions we use uppercase letters, whereas Boolean functions are denoted with lowercase letters.

Every vectorial Boolean function in n variables can be presented as

(x)=(f1(x),…,fn(x)),x∈F2n,

where f1,…,fn are Boolean functions in n variables called coordinate functions of F. An arbitrary nonempty linear combination of coordinate functions is called a component function of a vectorial function F. In terms of the inner product, which will be introduced in the next section, a component function is a function fv(x) = 〈F(x),v〉 for any nonzero ∈F2n. In particular, every coordinate function is a component function.

For example, :F23→F23 given by the truth tableis a vectorial Boolean function with coordinate functions f1 = (01010101), f2 = (00100001), and f3 = (11000010); we list here vectors of values of them. Note that the component functions of F are f1, f2, f3, f1 ⊕ f2 = (01110100), f1 ⊕ f3 = (10010111), f2 ⊕ f3 = (11100011), and f1 ⊕ f2 ⊕ f3 = (10110110).

x1x2x3

F(x1,x2,x3)

000

001

001

101

010

010

011

100

100

000

101

100

110

001

111

110

1.2 Algebraic Normal Form

Let ⊕ denote the addition modulo 2 (XOR). It is known that any Boolean function can be uniquely represented by its algebraic normal form (ANF):

(x1,…,xn)=⊕k=1n⊕i1,…,ikai1,…,ikxi1⋅⋯⋅xik⊕a0,

where for each k indices i1,…,ik are pairwise distinct and sets {i1,…,ik} are exactly all different nonempty subsets of the set {1,…,n}; coefficients i1,…,ik, a0 take values from 2. In the Russian mathematical literature, the ANF is usually called a Zhegalkin polynomial in honor of Ivan Zhegalkin (1869-1947), a Soviet mathematician who introduced such a representation in 1927.

For a Boolean function f, the number of variables in the longest item of its ANF is called the algebraic degree of a function (or briefly degree) and is denoted by deg(f). A Boolean function is affine, quadratic, cubic, and so on if its degree is not more than 1, or is equal to 2, 3, and so on, respectively.

For example, functions g and h given above have the ANFs g(x1,x2) = x1 ⊕ x2 ⊕ 1 and h(x1,x2,x3) = x1x2x3 ⊕ x1x2 ⊕ x1x3 ⊕ x2x3 and degrees 1 and 3,...

Produkt-Details

• Erscheint lt. Verlag: 24.8.2015
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Graphentheorie
• Themenwelt: Technik
• ISBN-10: 0-12-802555-7 / 0128025557
• ISBN-13: 978-0-12-802555-0 / 9780128025550