Cryptography Reference
In-Depth Information
As stated, the claim indicated that for a bijective C monomial, f ,givenany
hyperplane, H = π ( k ), if we have:
Df ( Ma,πx )+ Df ( πa, Mx )= Λ M Df ( πa, πx ) ,
(10)
for all a, x
k .
To prove that the statement as given in [15] is in err, let us define the space sav-
ing notation S f ( A, B )( a, x )= Df ( Aa, Bx )+ Df ( Ba, Ax ), and take the following
example. Let k = GF (64) over
k ,then M = M σ
π and Λ M = M σ + σ q θ ,forsome σ
F 2 , f ( x )= x 5 , πx = x + x 2 ,and Mx = x 4 + x 8 .
By a simple calculation,
S f ( M, π )( a, x )=( a 16 + a 32 )( x + x 2 )+( a + a 2 )( x 16 + x 32 )
= a 16 x + ax 16 + a 32 x + ax 32 + a 16 x 2 + a 2 x 16 + a 32 x 2 + a 2 x 32
= ax 4 + a 4 x + a 2 x 4 + a 4 x 2 + ax 8 + a 8 x + a 2 x 8 + a 8 x 2 16
= Df ( πa, πx ) 16 .
(11)
(Herewenotethattwotermsoftheform( a 4 + a 8 )( x 4 + x 8 ) cancelled each other in
the first line above.) Thus, we have found a counterexample with Λ M x = x 16 and
Mx =( πx ) 4 , which is certainly not the composition of a multiplication map and
π . Here the fact that 2 ( codim ( H )+ θ )= n created some extra symmetries in the
relations between the coecients of M and Λ M . Informally, θ was an exceptional
choice which permits the existence of a linear map allowing collisions between
monomials generated from Df ( Ma,πx )and Df ( πa, Mx ). Since the arithmetic
of k has characteristic 2, collision corresponds with annihilation.
We can resolve the minor issues with the result of Ding et al. and generalize
the statement somewhat by providing a more detailed analysis of the symmetry:
Df ( Ma,πx )+ Df ( πa, Mx )= Λ M Df ( πa, πx ) ,
(12)
for more general linear maps, π . In particular, a more precise formulation of the
result of Ding et al. is the special case of d = 1 in the following theorem.
and πx = i =0 x q i
f ( x )= x q θ +1
C map, and let
Theorem 3. Let
be a
M
Df ( Ma,πx )+ Df ( πa, Mx )= Λ M Df ( πa, πx ) .If θ + d< 2 ,
be linear. Suppose
|
n
3 θ
|
>d ,and 0 <d<θ
1 ,then M = M σ π for some σ
k .
Proof. Our strategy for the proof will be to determine relations between the co-
ecients of the linearized polynomial forms of M and Λ M . We will zigzag back
and forth between solving for coecients of M and of Λ M , further resolving the
relationship between the two maps with each step. We will extensively use the
“space of indices,” the torus consisting of the pairs ( r, s )(mod n ) which corre-
spond to monomials of the form a q r x q s . The geometry of this space of indices
will be useful in determining relations on the coecients of the corresponding
monomials in the expansions of (12).
 
Search WWH ::




Custom Search