Improved Upper Bound for the Relative Distance Between a Boolean Function and the Set of k -Dimensional Functions
- PDF / 104,253 Bytes
- 5 Pages / 594 x 792 pts Page_size
- 68 Downloads / 174 Views
IMPROVED UPPER BOUND FOR THE RELATIVE DISTANCE BETWEEN A BOOLEAN FUNCTION AND THE SET OF k-DIMENSIONAL FUNCTIONS UDC 519.7
A. N. Alekseychuk
Abstract. A theorem is proved that improves a previously upper bound for the relative distance between a Boolean function of n variables and the set of k-dimensional functions, k < n . The proof is based on the Bonami-Beckner inequality. Keywords: correlation cryptanalysis, k-dimensional Boolean function, bent function, Walsh–Hadamard transform, Bonami–Beckner inequality. We introduce the following notation: Vn is the set of binary vectors of length n; B n = { f | f :Vn ® {0, 1}} is the set of Boolean functions of n variables; # M is the cardinality of a set M ; d ( f , g ) = 2- n # {x ÎVn : f ( x ) ¹ g ( x )} is the relative distance between functions f , g Î B n ; d ( f , U ) = min d ( f , g ) is the relative distance from a function f Î B n to a set U Í B n . g ÎU
As usual, the set Vn is identified with an n-dimensional vector space over the field F = GF( 2). In this case, the sum of vectors a = ( a1 , ... , a n ) and x = ( x1 , ... , x n ) ÎVn is found by the formula a Å x = ( a1 Å x1 , K , a n Å x n ), and the Boolean scalar product is found by the formula ax = a1 x1 Å ××× Å a n x n (hereafter, the symbol Å denotes the operation of addition of elements of the field F and vectors over this field). Denote by Fn ´k the set of matrices of size n ´ k over the field F and by Ln , k the set of all k-dimensional subspaces of the vector space Vn , k = 0, 1, K , n . For any f Î B n and H Î Ln , k , we put $f ( a ) = 2- n
å ( -1) f (x) Å ax ,
xÎVn
w f (H ) = l f ( H ) = 2- k
a ÎVn ,
(1)
å f$ ( x )2 ,
xÎH
å å f$ ( x )( -1)a s x ,
sÎVk
xÎH
where a s (s ÎVk ) are representatives of all pairwise different cosets of the vector space Vn with respect to the subspace H ^ dual to H. Numbers (1) are called normalized Walsh–Hadamard coefficients of a function f. Note that, according to the Parseval equality, we have w f (Vn ) = 1. Moreover, the following equality holds (see, for example, Lemma 2.40 in [1]):
å $f ( x )( -1)a s x = 2- (n - k ) å^( -1) f (xÅ a s ) ,
which implies that l f ( H ) £ 1.
xÎH
H Î Ln , k ,
(2)
xÎH
Institute of Special Communication and Information Protection of the National Technical University of Ukraine “Kyiv Polytechnic Institute,” Kyiv, Ukraine, [email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 5, September–October, 2015, pp. 26–30. Original article submitted February 21, 2015. 1060-0396/15/5105-0687
©
2015 Springer Science+Business Media New York
687
A function g Î B n is called k-dimensional [2, 3], k = 1, 2, K , n - 1, if it is representable in the form (3)
g ( x ) = j( xA ) , x ÎVn ,
where j Î B k and A Î Fn ´k . Denote by B n , k the set of all k-dimensional functions of n variables. For any H Î Ln , k , denote by B n , k ( H ) the set that consists of all functions g Î B n , k representable in the form (3) for which the columns of the matrix A generate the subspace H. The following equality holds: Bn, k =
U
(4)
Data Loading...
