Bent Functions

Description

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

Front Cover 2
Bent Functions: Results and Applications to Cryptography 5
Copyright 6
Contents 7
Foreword 13
Preface 15
Notation 19
Chapter 1: Boolean Functions 21
- 1.1 Definitions 21
- Introduction 21
- 1.2 Algebraic Normal Form 23
- 1.3 Boolean Cube and Hamming Distance 24
- 1.4 Extended Affinely Equivalent Functions 26
- 1.5 Walsh-Hadamard Transform 27
- 1.6 Finite Field and Boolean Functions 28

Front Cover 2
Bent Functions: Results and Applications to Cryptography 5
Copyright 6
Contents 7
Foreword 13
Preface 15
Notation 19
Chapter 1: Boolean Functions 21
- 1.1 Definitions 21
- Introduction 21
- 1.2 Algebraic Normal Form 23
- 1.3 Boolean Cube and Hamming Distance 24
- 1.4 Extended Affinely Equivalent Functions 26
- 1.5 Walsh-Hadamard Transform 27
- 1.6 Finite Field and Boolean Functions 28
- 1.7 Trace Function 29
- 1.9 Trace Representation of a Boolean Function 31
- 1.8 Polynomial Representation of a Boolean Function 31
- 1.10 Monomial Boolean Functions 34
Chapter 2: Bent Functions: An Introduction 37
- Introduction 37
- 2.1 Definition of a Nonlinearity 37
- 2.2 Nonlinearity of a Random Boolean Function 38
- 2.3 Definition of a Bent Function 38
- 2.4 If n Is Odd? 40
- 2.5 Open Problems 41
- 2.6 Surveys 43
Chapter 3: History of Bent Functions 45
- Introduction 45
- 3.1 Oscar Rothaus 45
- 3.2 V.A. Eliseev and O.P. Stepchenkov 46
- 3.3 From the 1970s to the Present 48
Chapter 4: Applications of Bent Functions 51
- Introduction 51
- 4.1 Cryptography: Linear Cryptanalysis and Boolean Functions 51
- 4.2 Cryptography: One Historical Example 52
- 4.3 Cryptography: Bent Functions in CAST 54
- 4.4 Cryptography: Bent Functions in Grain 55
- 4.5 Cryptography: Bent Functions in HAVAL 56
- 4.6 Hadamard Matrices and Graphs 57
- 4.7 Links to Coding Theory 58
- 4.8 Bent Sequences 59
- 4.9 Mobile Networks, CDMA 60
- 4.10 Remarks 62
Chapter 5: Properties of Bent Functions 63
- 5.1 Degree of a Bent Function 63
- Introduction 63
- 5.2 Affine Transformations of Bent Functions 64
- 5.4 Dual Bent Functions 65
- 5.3 Rank of a Bent Function 65
- 5.5 Other Properties 66
Chapter 6: Equivalent Representations of Bent Functions 69
- 6.2 Difference Sets 69
- Introduction 69
- 6.1 Hadamard Matrices 69
- 6.3 Designs 70
- 6.4 Linear Spreads 70
- 6.5 Sets of Subspaces 71
- 6.6 Strongly Regular Graphs 72
- 6.7 Bent Rectangles 72
Chapter 7: Bent Functions with a Small Number of Variables 75
- 7.1 Two and Four Variables 75
- Introduction 75
- 7.2 Six Variables 76
- 7.3 Eight Variables 79
- 7.4 Ten and More Variables 80
- 7.5 Algorithms for Generation of Bent Functions 81
- 7.6 Concluding Remarks 82
Chapter 8: Combinatorial Constructions of Bent Functions 83
- 8.1 Rothaus's Iterative Construction 83
- Introduction 83
- 8.2 Maiorana-McFarland Class 84
- 8.3 Partial Spreads: PS+, PS- 85
- 8.4 Dillon's Bent Functions: PSap 86
- 8.5 Dobbertin's Construction 87
- 8.6 More Iterative Constructions 87
- 8.7 Minterm Iterative Constructions 88
- 8.8 Bent Iterative Functions: BI 89
- 8.9 Other Constructions 92
Chapter 9: Algebraic Constructions of Bent Functions 93
- 9.1 An Algebraic Approach 93
- Introduction 93
- 9.2 Bent Exponents: General Properties 94
- 9.3 Gold Bent Functions 95
- 9.4 Dillon Exponent 96
- 9.5 Kasami Bent Functions 96
- 9.6 Canteaut-Leander Bent Functions (MF-1) 98
- 9.7 Canteaut-Charpin-Kuyreghyan Bent Functions (MF-2) 98
- 9.8 Niho Exponents 99
- 9.9 General Algebraic Approach 100
- 9.10 Other Constructions 100
Chapter 10: Bent Functions and Other Cryptographic Properties 101
- Introduction 101
- 10.1 Cryptographic Criteria 101
- 10.2 High Degree and Balancedness 102
- 10.3 Correlation Immunity and Resiliency 102
- 10.4 Algebraic Immunity 103
- 10.5 Vectorial Bent Functions, Almost Bent Functions, and Almost Perfect Nonlinear Functions 105
Chapter 11: Distances Between Bent Functions 109
- 11.1 The Minimal Possible Distance BetweenBent Functions 109
- Introduction 109
- 11.2 Classification of Bent Functions at the Minimal Distance from the QuadraticBent Function 110
- 11.3 Upper Bound for the Number of Bent Functions at the Minimal Distance from an Arbitrary Bent Function 113
- 11.4 Bent Functions at the Minimal Distance from a McFarland Bent Function 114
- 11.5 Locally Metrically Equivalent Bent Functions 114
- 11.6 The Graph of Minimal Distances ofBent Functions 115
Chapter 12: Automorphisms of the Set of Bent Functions 117
- 12.1 Preliminaries 117
- Introduction 117
- 12.2 Shifts of the Class of Bent Functions 118
- 12.3 Duality Between Definitions of Bent and Affine Functions 122
- 12.4 Automorphisms of the Set of Bent Functions 124
- 12.5 Metrically Regular Sets 125
Chapter 13: Bounds on the Number of Bent Functions 127
- Introduction 127
- 13.1 Preliminaries 127
- 13.2 The Number of Bent Functions for Small n 128
- 13.3 Upper Bounds 128
- 13.4 Direct Lower Bounds 131
- 13.5 Iterative Lower Bounds 132
- 13.6 Lower Bound from the Bent Iterative Functions 134
- 13.7 Testing of the Lower Bound for Small n 138
- 13.8 Asymptotic Problem and Hypotheses 140
Chapter 14: Bent Decomposition Problem 143
- Introduction 143
- 14.1 Preliminaries 143
- 14.2 Partial Results 144
- 14.3 Boolean Function as the Sum of a Constant Number of Bent Functions 145
- 14.4 Any Cubic Boolean Function in Eight Variables is the Sum of at Most Four Bent Functions 147
- 14.5 Decomposition of Dual Bent Functions 148
Chapter 15: Algebraic Generalizations of Bent Functions 153
- 15.1 Preliminaries 153
- Introduction 153
- 15.2 The q-Valued Bent Functions 154
- 15.3 The p-ary Bent Functions 157
- 15.4 Bent Functions Over a Finite Field 159
- 15.6 Generalized Boolean Bent Functions (of Schmidt) 161
- 15.5 Bent Functions Over Quasi-Frobenius Local Rings 161
- 15.7 Bent Functions from a Finite Abelian Group into the Set of Complex Numbers on the Unit Circle 164
- 15.8 Bent Functions from a Finite Abelian Group into a Finite Abelian Group 165
- 15.9 Non-Abelian Bent Functions 167
- 15.10 Vectorial G-Bent Functions 168
- 15.11 Multidimensional Bent Functions on a Finite Abelian Group 169
Chapter 16: Combinatorial Generalizations of Bent Functions 171
- 16.1 Symmetric Bent Functions 171
- Introduction 171
- 16.2 Homogeneous Bent Functions 172
- 16.3 Rotation-Symmetric Bent Functions 172
- 16.4 Normal Bent Functions 175
- 16.5 Self-Dual and Anti-Self-Dual Bent Functions 176
- 16.6 Partially Defined Bent Functions 178
- 16.7 Plateaued Functions 178
- 16.8 Z-Bent Functions 179
- 16.9 Negabent Functions, Bent4-Functions, and I-Bent Functions 180
Chapter 17: Cryptographic Generalizations of Bent Functions 183
- 17.1 Semibent Functions (Near-Bent Functions) 183
- Introduction 183
- 17.2 Balanced (Semi-) Bent Functions 185
- 17.3 Partially Bent Functions 186
- 17.4 Hyperbent Functions 188
- 17.5 Bent Functions of Higher Order 191
- 17.6 k-Bent Functions 192
References 195
Index 217

Author's affiliation

Natalia Tokareva: Sobolev Institute of Mathematics, Siberian Br

Results and Applications to Cryptography

Description

TOC

Reviews (0)

Author's affiliation