Counting Boolean Functions with Faster Points

Date

2019-03-31

Author

Salagean, Ana
Özbudak, Ferruh

Metadata

Show full item record

Item Usage Stats

216
views

0
downloads

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ălăgean and Mandache-Sălăgean 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.

Subject Keywords

Boolean functions, Differential attacks, Linear structures

URI

https://hdl.handle.net/11511/83466

Conference Name

The Eleventh International Workshop on Codingand Cryptography (31 Mart - 05 Nisan 2019)

Collections

Department of Mathematics, Conference / Seminar

Suggestions

OpenMETU
Core

Counting Boolean functions with faster points Salagean, Ana; Özbudak, Ferruh (Springer Science and Business Media LLC, 2020-09-01) 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 Salagean and Mandache-Salagea...
Characterisation and enumeration of a class of semi bent quadratic Boolean functions KOÇAK, Neşe; Koçak, Onur Ozan; Özbudak, Ferruh; SAYGI, ZÜLFÜKAR (2015-01-01) In this paper, we consider semi-bentness of quadratic Boolean functions defined for even n and give the characterisation of these functions. Up to our knowledge, semi-bentness of this class has not been investigated before and we proved that semi-bent functions of this form exist only for 6|n. Furthermore, we present a method for enumeration of semi-bent and bent functions in certain classes. Using this method we find the exact number of semi-bent functions of this form. Moreover, we complete some previous ...
On finite groups admitting a fixed point free abelian operator group whose order is a product of three primes Mut Sağdıçoğlu, Öznur; Ercan, Gülin; Department of Mathematics (2009) A long-standing conjecture states that if A is a finite group acting fixed point freely on a finite solvable group G of order coprime to jAj, then the Fitting length of G is bounded by the length of the longest chain of subgroups of A. If A is nilpotent, it is expected that the conjecture is true without the coprimeness condition. We prove that the conjecture without the coprimeness condition is true when A is a cyclic group whose order is a product of three primes which are coprime to 6 and the Sylow 2-sub...
Method of Lyapunov functions for differential equations with piecewise constant delay Akhmet, Marat; ARUĞASLAN ÇİNÇİN, Duygu; Yılmaz, Elanur (2011-06-15) We address differential equations with piecewise constant argument of generalized type [5-8] and investigate their stability with the second Lyapunov method. Despite the fact that these equations include delay, stability conditions are merely given in terms of Lyapunov functions; that is, no functionals are used. Several examples, one of which considers the logistic equation, are discussed to illustrate the development of the theory. Some of the results were announced at the 14th International Congress on C...
Generalized rotation symmetric and dihedral symmetric boolean functions - 9 variable boolean functions with nonlinearity 242 Kavut, Selcuk; Yucel, Melek Diker (2007-12-20) Recently, 9-variable Boolean functions having nonlinearity 241, which is strictly greater than the bent concatenation bound of 240, have been discovered in the class of Rotation Symmetric Boolean Functions (RSBFs) by Kavut, Maitra and Yucel. In this paper, we present several 9-variable Boolean functions having nonlinearity of 242, which we obtain by suitably generalizing the classes of RSBFs and Dihedral Symmetric Boolean Functions (DSBFs). These functions do not have any zero in the Walsh spectrum values, ...

Citation Formats

A. Salagean and F. Özbudak, “Counting Boolean Functions with Faster Points,” presented at the The Eleventh International Workshop on Codingand Cryptography (31 Mart - 05 Nisan 2019), 2019, Accessed: 00, 2021. [Online]. Available: https://hdl.handle.net/11511/83466.