Counting Boolean functions with faster points
- PDF / 354,734 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 33 Downloads / 226 Views
Counting Boolean functions with faster points 1 Ana Sal ˘ agean ˘
· Ferruh Özbudak2
Received: 29 May 2019 / Revised: 28 January 2020 / Accepted: 5 February 2020 © The Author(s) 2020
Abstract Duan and Lai introduced the notion of “fast point” for a Boolean function f as being a direction a so that the algebraic degree of the derivative of f in direction a is strictly lower than the expected deg( f ) − 1. Their study was motivated by the fact that the existence of fast points makes many cryptographic differential attacks (such as the cube and AIDA attack) more efficient. The number of functions with fast points was determined by Duan et al. in some special cases and by S˘al˘agean and Mandache-S˘al˘agean in the general case. We generalise the notion of fast point, defining a fast point of order as being a fast point a so that the degree of the derivative of f in direction a is lower by at least than the expected degree. We determine an explicit formula for the number of functions of degree d in n variables which have fast points of order . Furthermore, we determine the number of functions of degree d in n variables which have a given number of fast points of order , and also the number of functions which have a given profile in terms of the number of fast points of each order. We apply our results to compute the probability of a function to have fast points of order . We also compute the number of functions which admit linear structures (i.e. their derivative in a certain direction is constant); such functions have a long history of being used in the analysis of symmetric ciphers. Keywords Boolean functions · Differential attacks · Linear structures Mathematics Subject Classification 94A60 · 11T55
This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Coding and Cryptography 2019”.
B
Ana S˘al˘agean [email protected] Ferruh Özbudak [email protected]
1
Department of Computer Science, Loughborough University, Loughborough, UK
2
Department of Mathematics and Institute of Applied Mathematics, Middle East Technical University, Ankara, Turkey
123
A. S˘al˘agean, F. Özbudak
1 Introduction Boolean functions used in cryptography are usually required to resist a range of attacks. They need to have a sufficiently high algebraic degree (i.e. the degree of the function written in its algebraic normal form) in order to resist algebraic attacks. Differential attacks on cryptographic functions typically exploit properties of the discrete derivative. The discrete derivative of a function f in the direction a is defined as Da f (x) = f (x + a) − f (x). The derivatives should also have a high degree; the highest that can be achieved is one less than the degree of the original function, i.e. deg(Da f ) ≤ deg( f )−1. Higher order derivatives of order k are obtained by differentiating k times in several directions. The higher order derivatives should also have a sufficiently high degree (the maximum possible being deg( f ) − k)). For example, the cube attack o
Data Loading...
