Cryptography Reference
In-Depth Information
5 Cryptographic Properties of Equivalence Classes
Let f ∈ B n and
M k 1 + i 1
1
b 0 ,M k 1 + i 2
b 0 , ..., M k 1 + i w
1 f =
{
b 0 }
,
1
1
where M 1 is the generator matrix of the sequence and 0
i 1 <i 2 < ... < i w
q
2. Clearly, any g
f can be represented by
M k 2 + i 1
j
b 0 ,M k 2 + i 2
b 0 , ..., M k 2 + i w
1 g =
{
b 0 }
,
j
j
where 1
j
φ ( q
1) /n , M j
is a generator matrix and 0
k 2
q
2. Let
f =
denote the equivalence class to which f belongs. Since
thesamekeystreamcanbegenerated by using Boolean functions of the same
equivalence class as filter functions, to assess the resistance to a certain type of
attack, we should define the corresponding cryptographic criteria by using the
weakest equivalent function. Define
{
g
B n |
g
f
}
deg( f )=min
g∈f
deg( g ) ,
AI
( f )=min
g∈f AI
( g ) ,
and
nl ( f )=min
g∈f
nl ( g ) .
To resist many kinds of attacks, deg( f ),
( f )and nl ( f ) should all be high. More-
over, every function equivalent to f should have a good immunity against fast al-
gebraic attacks. Clearly, for the function f 1 inExample1,wehavedeg( f 1 )=1,
AI
AI
( f 1 )=1and nl ( f 1 ) = 0, which are very bad.
The number of variables of f , denoted by var ( f ), is the number of variables
appearing in its ANF. Define
var ( f )=min
g∈f
var ( g )
To be implemented eciently, var ( f ) should be small.
Lemma 1. Let f
B n . Then we have deg( f )
n
1 , which is a tight bound.
Proof. Since ( x 1 +1)( x 2 +1)
···
( x n +1) is of degree n ,oneof f and f +
( x 1 +1)( x 2 +1)
···
( x n +1) is of degree n , and the other is not. Therefore,
deg( f )
1. In the next section, we can find that there exist many f such
that deg( f )= n
n
1, and the result follows.
Lemma 2. Let f
B n . If there is a balanced function g such that g
f ,then
deg ( f )
var ( f )
1 .
Proof. Let var ( f )= m .If m = n , then by Lemma 1 the result follows. If m<n ,
then there is an h
B n such that the number of variables appearing in its ANF
= k 2 n−m ,where k is an integer. Since h is equivalent to a
balanced function, we have
is m . Therefore,
|
1 h |
=2 n− 1 + c ,where c =0or
1. Therefore, c =0
and h is balanced. We regard h as an m -variable function, that is, h
|
1 h |
±
B m .Then
h is balanced and deg( h )
m
1.
Search WWH ::




Custom Search