On Hidden Sums Compatible with A Given Block Cipher Diffusion Layer
Carlo Brunetta Marco Calderini Massimiliano Sala

























δ̣

ϵ
η̅
#1#1_2
 ⟹ 
K
#1#1
w̅
z̅
#1#1




















sistema
  {[ .

𝐀
𝐂
𝐃
𝐅
𝐏
𝐍
𝐒
𝐕
𝐙
𝐓
𝐞
𝐮̆
𝐯̌
𝐱
𝐲
𝐳
𝒜
ℬ
𝒞
𝒟
ℰ
ℱ
𝒢
ℐ
ℋ
𝒥
𝒦
ℒ
ℳ
𝒩
𝒬
𝒪
𝒫
ℛ
𝒮
𝒯
𝒰
𝒱
𝒲
𝒳
𝒴
𝒵
łℓ

𝕂
PG



÷
minmin









𝔽_q^2
𝔽
𝔽_ℓ^2
𝔽_ℓ


𝔽_2^n
2𝔽_2
𝔽_2^m
q̅
𝔽̅_q
𝐅r






















































Φ
Supp
Φ
X_∞
Im








































































𝔽_q
2𝔽_2
𝔽_p





theoremTheorem[section]

remark[theorem]Remark

lemma[theorem]Lemma
definition[theorem]Definition
example[theorem]Example

proposition[theorem]Proposition

criterio[theorem]Criterio

corollary[theorem]Corollary
con[theorem]Conjecture
algorithmAlgorithm[section]














 









tn]Carlo Brunetta
brunetta@unitn.it
no]Marco Calderini cor1
marco.calderini@uib.no
tn]Massimiliano Sala
maxsalacodes@gmail.com




  

  


[tn]Department of Mathematics, University of Trento, Via Sommarive 14,
38100 Povo (Trento), Italy
[no]Department of Informatics, University of Bergen, Thormøhlensgate 55, 5008 Bergen, Norway
[cor1]Corresponding author







Sometimes it is possible to embed an algebraic trapdoor into a block cipher. Building on previous research, in this paper
we investigate an especially dangerous algebraic structure, which is called a hidden sum and which is related
to some regular subgroups of the affine group. Mixing group theory arguments and cryptographic tools, we pass from
characterizing our hidden sums to designing an efficient algorithm to perform the necessary preprocessing for the
exploitation of the trapdoor.




Hidden sums, trapdoor, mixing layer, cryptography, block ciphers.








§ INTRODUCTION

Sometimes it is possible to embed an algebraic trapdoor into a block cipher. Building on previous research, in this paper
we investigate an algebraic structure, which is called a hidden sum and which is related
to some regular subgroups of the affine group. To be more precise, in <cit.>, the authors study some elementary abelian regular subgroups of the affine general linear group acting on a space V=(_2)^N, in order to construct a trapdoor for a class of block ciphers.
These subgroups induce alternative operations ∘ on V, such that (V,∘) is a vector space over _2. In <cit.>, it is shown that for a class of these operations,  which we will call practical hidden sums, it is possible to represent the elements with respect to a fixed basis of (V,∘) in polynomial time. Moreover, an estimate on the number of these operations is given.
Using this class of hidden sums, the authors provide an attack, which works in polynomial time, on ciphers that are vulnerable to this kind of trapdoor.

In this article we continue the analysis started in <cit.>. In Section 3 we give a lower bound on the number of practical hidden sums, comparing also this value with a previous upper bound.  From these bounds it is obvious that it is not feasible to generate all possible practical hidden sums due to the large number of these even in small dimensions, e.g. for N=6 we have ∼2^23 practical hidden sums.
In Section 4 we study the problem of determining the possible maps which are linear with respect to a given practical hidden sums. More precisely, we provide an algorithm that takes as input a given linear map   (with respect to the usual XOR on V) and returns  some operations ∘, which can be defined over V, that are different from the XOR and for which the map  is linear, i.e. (x∘ y)=(x)∘(y) for all x, y in V. Our aim is to individuate a family of hidden sums that can weaken the components of a given cipher, or to design a cipher containing the trapdoor based on hidden sums.
In the last section we apply the procedure given in Section 3 to the mixing layer of the cipher PRESENT <cit.>, yelding a set of hidden sums which linearize this permutation matrix and might in principle be used to attack the cipher.




§ PRELIMINARIES AND MOTIVATIONS


We write  to denote the finite field of q elements, where q is a prime power , and ()^s× t to denote the set of all matrices with entries over  with s rows and t columns. The identity matrix of size s is denoted by I_s.
We use 

    _i=(0,…,0_i-1,1,0,…,0_N-i)∈ ()^N

to denote the unit vector, which has a 1 in the ith position, and zeros elsewhere. Let m≥ 1, the vector (sub)space generated by the vectors _1,…,_m is denoted by {_1,…,_m}.

Let V=()^N, we denote respectively by (V), (V) the symmetric and the alternating group acting on V.   We will denote the translation with respect  to a vector ∈ V by _:↦+, and T(V,+) will denote the translations on the vector space (V,+), that is, T(V,+)={_|∈ V}. By (V ,+) and (V ,+) we denote the affine and linear groups of V. We write ⟨ g_1,…,g_m⟩ for the group generated by g_1,…,g_m in (V). The map 1_V will denote the identity map on V.

Let G be a finite group acting  on V. We write the action of a permutation g ∈ G on a vector ∈ V as g. 

 We recall that a permutation group G acts regularly (or is regular) on V if for any pair ,∈ V there exists a unique map g in G such that g=. Moreover, an elementary abelian group (or elementary abelian p-group) is an abelian group such that any nontrivial element has order p. In particular, the group of translations acting on V, T(V,+), is a regular elementary abelian group.












 §.§ Block ciphers and hidden sums

Most modern block ciphers are iterated ciphers, i.e. they are obtained by the composition of a finite number ℓ of rounds.




 Several classes of iterated block ciphers have been proposed, e.g. substitution permutation network <cit.> and key-alternating block cipher <cit.>. Here we present one more recent definition <cit.> that determines a class large enough to include some common ciphers (AES <cit.>, SERPENT <cit.>, PRESENT <cit.>), but with enough algebraic structure to allow for security proofs,  in the contest of symmetric cryptography. In particular, about properties of the groups related to the ciphers.

Let V=(_2)^N with N=mb and b≥ 2. The vector space V is a direct sum

    V=V_1⊕…⊕ V_b,

where each V_i has the same dimension m (over _2). For any ∈ V, we will write =_1⊕…_b, where _i∈ V_i. 

Any γ∈(V) that acts as γ=_1γ_1⊕…⊕_bγ_b, for some γ_i's in (V_i), is a bricklayer transformation (a “parallel map”) and any γ_i is a brick. Traditionally, the maps γ_i's are called S-boxes and γ a “parallel S-box”. A linear map :V→ V is traditionally said to be a “Mixing Layer” when used in composition with parallel maps. 
For any I⊂{1,…,b}, with I∅, {1,…,b}, we say that ⊕_i∈ I V_i is a wall. 

A linear map ∈(V ,+) is a proper mixing layer if no wall is invariant under .


We can characterize the translation-based class by the following:

 A block cipher  𝒞 = {φ_k | k  ∈𝒦}⊂(V), where  is the set containing all the session keys and φ_k are keyed permutations, over
  _2 is called translation based (tb) if:
       
    
  * it is the composition of a finite number of ℓ rounds, such that any round ρ_k,h can be written[we drop the round indices] as γ_k̅, where
    
    
  - γ is a round-dependent bricklayer transformation (but it does not depend on k),
     
  - λ is a round-dependent linear map (but it does not depend on k),
    
  - k̅ is in V and depends on both k and the round (k̅ is called a “round key”),
     
     
      
  * for at least one round, which we call proper, we have (at the same time) that  is proper and that the map 𝒦→ V given by k ↦k̅ is
      surjective.
    








For a tb cipher it is possible to define the following groups.
For each round h

    Γ_h() = ⟨_k,h| k∈⟩⊆(V),

and the round function group is given by

    Γ_∞()=⟨Γ_h() | h=1,…,ℓ⟩.


An interesting problem is determining the properties of the permutation group Γ_∞(𝒞)=Γ_∞  that imply  weaknesses of the cipher. 
A trapdoor  (sometimes called backdoor see <cit.>) is a hidden structure of the cipher, whose knowledge allows an attacker to obtain information on the key or to decrypt certain ciphertexts.

The first paper dealing with properties of Γ_∞ was published by Paterson <cit.>, who showed  that if this group is imprimitive, then it is possible to embed a trapdoor into the cipher. 
On the other hand, if the group is primitive no such trapdoor can be inserted. 
Other works, dealing with security properties of ciphers related to groups theory, study also whenever the group generated by the round functions is large <cit.>. However, as shown in <cit.>, even if a given set of round functions generates a large permutation group, it might be possible to approximate these round function by another set of round functions which generates a small group.

Similarly, the primitivity of Γ_∞ does not guarantee the absence of  other types of trapdoors based on the group structure of Γ_∞. For example, if the group
is contained in (V) (which is a primitive group), the encryption function is affine and  once we know the image of a basis of V and the image of the zero vector, then we are able to reconstruct the matrix and the translation that compose the map. This motivated the authors of <cit.> on studying different abelian operations, which can be individuate on V in order to embed a trapdoor into a block cipher.  The authors in <cit.> called these operations hidden sums.


In the remainder of this section, we summarize the theory presented in <cit.>.

If T⊂(V) is an elementary abelian regular group  acting on V,  then there exists a vector space structure (V,∘) such that T is the related translation group. In fact, since T is regular the elements of the group can be labelled 
    T={_|∈ V},
 where _ is the unique map in T such that 0↦. Then, the sum between two elements is defined by ∘:=_. Clearly, (V,∘) is an abelian additive group and thus a vector space over _2.

Conversely, if (V,∘) is a vector space over 2, then its translation group, given by the maps _:↦∘, is an elementary abelian group acting regularly on V.




In the following, with the symbol + we refer to the usual sum over the vector space V. We denote by T_+=T(V,+), (V,+) and (V,+), respectively, the translation, affine and linear groups w.r.t. +. We use T_∘, (V,∘) and (V,∘) to denote, respectively, the translation, affine and linear groups corresponding to a hidden sum ∘.  That is, T_∘={_|∈ V} where _:↦∘, (V,∘) is the group of the maps  such that (∘)=∘ for all ,∈ V, and any map in (V,∘) is the composition of a map ∈(V,∘) and a map  _∈ T_∘.

Since we will focus on a particular class of these operation ∘, we define a hidden sum any vector space structure (V,∘), different from the usual (V,+), such that T_+⊆(V,∘). While, a practical hidden sum is a hidden sum such that T_∘ is also contained in (V,+).

From <cit.> we have three interesting problems: 


  * Determine the operations ∘ (equivalently the translation groups T_∘) such that T_+⊆(V,∘).

  * Determine the operations ∘  such that T_∘⊆(V,+) (i.e. those which are practical hidden sums).

  * Given a parallel S-box γ and a mixing layer , determine the operations ∘ such that γ, ∈(V,∘) or γ∈(V,∘).

 Problem 1 is related to identifying the class of hidden sums that could potentially contain Γ_∞(), of a given cipher , in the group (V,∘) since T_+⊆Γ_∞(); or at least to individuating hidden sums for which the XOR with a round key is affine with respect to the operation ∘. 

Operations with the characteristic given in Problem 2 and that of Problem 1 permit to represent an element  in (V,∘) efficiently, as we will see in Algorithm <ref>. 

The last problem permits to understand if a given block cipher could be modified to introduce the algebraic structure of a hidden sum.


The following vector space plays an important role for studying these problems. Let T be any subgroup of the affine group, we can define the vector space 

    U(T)={∈ V|_∈ T}.

In <cit.> the authors proved

Let V=(_2)^N, (V)=N. Let T⊆(V,+) be an elementary abelian regular subgroup. If T T_+, then 1≤(U(T))≤ N-2.


A characterization is given in <cit.> for the maps that generate a translation group T_∘⊆(V,+) such that T_+⊆(V,∘).
We recall that for every , _∈ T_∘⊂(V,+) can be written as __ for a linear map _∈(V,+). We will denote by Ω(T_∘)={_|∈ V}⊂(V,+). Moreover _=1_V if and only if ∈ U(T_∘).

 We recall the following definition.

An element r of a ring R is called nilpotent if r^m=0 for some m≥ 1 and it is called unipotent if r-1 is nilpotent, i.e. (r-1)^m=0 for some m≥ 1. 

Let G⊆(V,+) be a subgroup consisting of unipotent permutations, then G is called unipotent.

 

Let T_∘⊆(V,+). We have that Ω(T_∘) is unipotent. Moreover, for all ∈ V _^2=1_V.



 Let N=n+d and V=(_2)^N, with n≥ 2 and d≥ 1. Let T_∘⊆(V,+) be such that U(T_∘)={_n+1,…,_n+d}. Then, T_+⊆(V,∘) if and only if for all _∈Ω(T_∘) there exists a matrix B_∈ (_2)^n× d such that

    _=[[ I_n  B_;   0 I_d ]].


Note that we can always suppose that  U(T_∘) is generated by the last vectors of the canonical basis, as any group T_∘ is conjugated to a group T_∘' such that U(T_∘')={_n+1,…,_n+d} (see <cit.>). 

 Indeed, let T_∘ be a translation group of a practical hidden sum, with U(T_∘)={_1,…,_d}. We have that _1,…,_d are linear independent with respect to the sum +, which implies that there exists a linear map g∈ GL(V,+) such that _ig=_n+i for i=1,…,d. Thus, the conjugated group T_∘'=gT_∘ g^-1 is such that U(T_∘')={_n+1,…,_n+d} and ∘' is again a practical hidden sum.

Practical hidden sums with U(T_∘)={_n+1,…,_n+d} are easier to study thanks to the particular structure reported in Theorem <ref>. 


When U(T_∘) is generated by the last vectors of the canonical basis, then the maps __i generate T_∘, i.e. the canonical vectors form a basis also for the vector space (V,∘).  Indeed, thanks to the form of the maps __i given in Theorem <ref>, it is possible to verify that combining the maps __i's we are able to obtain all the 2^N different maps contained in T_∘ (see <cit.> for further details).


In <cit.> it turns out that for any practical hidden sum T_∘⊆(V,+), any given vector  can be represented in (V,∘), with respect to the canonical vectors, in polynomial time ((N^3)). 
 Let T_∘ be a practical hidden sum with U(T_∘)={_n+1,…,_n+d} ((V)=N=n+d), then the algorithm for determining the representation of a given vector  is the following

Correctness of Algorithm <ref>:

To find the coefficients _1,…,_N is equivalent to individuating the maps __i which generate the map _. So, we need to understand which maps (among  the __i)  are needed to send 0 in , or equivalently  in 0 (since T_∘ is an elementary regular subgroups, _ is the unique map such that 0_= and  _=0).

Note that thanks to the form of the maps __i given in Theorem <ref>, whenever we apply a map __i to a vector , the first n entries of  are left unchanged. So, if the entry v_i is equal to 1 for 1≤ i≤ n, to delete it we need to apply __i. This explains step [ii]. 

Now, '=__1^_1⋯__n^_n is such that the first n entries are all zero. So, we need to delete the entry v'_j for n+1≤ j≤ N, whenever v'_j=1. Since __j=__j for n+1≤ j≤ N, we apply __j if v'_j=1.

So, we have obtained a map ∈ T_∘ such that =0, and since this is unique we have =_.


Note that if U(T_∘) is not generated by the last vectors of the canonical basis, then we can consider the conjugated group T_∘'=gT_∘ g^-1, with g as above, and we need to apply Algorithm <ref> to g, obtaining its representation in (V,∘'). This leads us to obtain the representation of  in (V,∘) with respect to the basis {_1 g^-1,...,_N g^-1} of (V,∘). In particular, the map g is an isomorphism of vector space between (V,∘) and (V,∘').


From this, the authors proved that a hidden sum trapdoor is practical, whenever Γ_∞⊆(V,∘) and T_∘⊆(V,+).

A class of these practical hidden sums is used in <cit.> to weaken the non-linearity of some APN S-boxes. In addition, in  <cit.> a differential attack with respect to hidden sums is presented.



An upper bound on the number of some hidden sums is given in <cit.> and reported below.

Let n≥ 2 and d≥ 1.  According to Theorem <ref>, denote the matrix __i by

    __i=[[           b^(i)_1,1         … b^(i)_1,d;       I_n         ⋮                   ⋮;           b^(i)_n,1         … b^(i)_n,d;         0                 I_d           ]],

for each 1≤ i≤ n.

Let N=n+d and V=(_2)^N, with n≥ 2 and d≥ 1. The number of elementary abelian regular subgroups T_∘⊆(V,+) such that (U(T_∘))=d and T_+⊆(V,∘) is

    N d_2· |(_n,d)|

where  (_n,d) is the variety of the ideal _n,d⊂_2[b^(s)_i,j|1≤ i,s≤ n,  1≤ j≤ d] generated by 

    _0∪_1∪_2∪_3

with

    _0   ={(b^(s)_i,j)^2-b^(s)_i,j|1≤ i,s≤ n,  1≤ j≤ d}
    _1   ={∏_i=1^n∏_j=1^d(1+∑_s∈ Sb^(s)_i,j)| S⊆{1,…,n},S∅},
    _2   ={b^(s)_i,j-b^(i)_s,j|1≤ i,s≤ n,  1≤ j≤ d},
    _3   ={b^(i)_i,j|1≤ i≤ n,  1≤ j≤ d},

and N d_q=∏_i=0^d-1q^N-i-1/q^d-i-1 is the Gaussian Binomial.




Let _n,d defined as in Theorem <ref>, then

    |(_n,d)|≤ 2^dn(n-1)/2-1-∑_r=1^n-2n r∏_1^n-r2(2^d-1)=μ(n,d).






§ NEW LOWER BOUNDS AND ASYMPTOTIC ESTIMATES


In this section we will provide a lower bound on the cardinality of the variety (_n,d). Moreover we will show that the ratio between the upper bound and lower bound is less than e^2^d+1/2^d(2^d-1).



From Theorem <ref> and from Remark <ref>, we have that a group T_∘ with U(T_∘)={_n+1,…,_n+d} is determined by the maps __i's, and in particular by B__1,…,B__n (B__i=0 for n+1≤ i≤ n+d). 
 Thus, we need to construct the matrices B__1,…,B__n so that:






  i) (U(T_∘))=d. Then for any ∈{_1,…, _n}, B_≠ 0. Indeed, ∈ U(T_∘) if and only if B_ =0. Moreover, 
		for any =(v_1,…,v_n+d)∈ V we have 

		
    _ = [[              I_n ∑_i=1^n v_i B__i;                0              I_d ]]


		and so we get that B_ = ∑_i=1^n v_i B__i (see Lemma 5.4 in <cit.>).

		This implies that every non-null linear combination of B__1,…,B__n is non-zero.  Note that, in Theorem <ref>, this condition is given by _1.


  ii) T_∘ is abelian. This happens if and only if the  ith row of B__j is equal to the jth row of B__i, obtaining the set _2.


  iii) T_∘ is elementary, that is, _^2=1_V for all . Then _ fixes  and, in particular, __i fixes _i. This is equivalent to having the ith row  of  B__i equals to 0, which is expressed by _3. 



Consider now any matrix B__i. Its size is n× d, thus any row of B__i can be written as an element of _2^d. Let us define the matrix 𝔅_∘=[B__1… B__n]∈ (_2^d)^n× n. From Condition i), ii) and iii), above, we have the following properties for  𝔅_∘:


  (I) 𝔅_∘ is full rank over _2,  when seen as an element of (_2)^n× nd. This guarantees that (U(T_∘)) = d.

  (II) 𝔅_∘ is symmetric.  Since the ith row of B__j is equal to the jth row of B__i we have that the entry (i,j) of 𝔅_∘ is equal to the entry (j,i).

  (III) 𝔅_∘ is zero-diagonal, as the ith row of B__i is zero for all i.


 

Let N = 5 and d=2 and consider the operation ∘ defined by the following B__i's:


    B__1  = [ 0 0; 1 1; 1 1 ] , B__2  = [ 1 1; 0 0; 0 1 ]
    B__3 = [ 1 1; 0 1; 0 0 ] ,
     B__4 = [ 0 0; 0 0; 0 0 ]  , B__5 = [ 0 0; 0 0; 0 0 ]

Since we have n = N-d = 3, we just need to focus on B__1, B__2 and B__3.

Representing the rows of the matrices as elements of 𝔽_2^2 = {0,1,α,α+1}, where α^2 = α + 1, we can rewrite the matrices as 


    B__1  = [     0; α + 1; α + 1 ], B__2  = [ α + 1;     0;     α ],
    B__3 = [ α + 1;     α;     0 ]

and so we can rewrite 𝔅_∘ as

    𝔅_∘ = [ B__1 B__2 B__3 ] = [    0 α +1 α +1; α +1    0    α;  α+1    α    0 ]





In Theorem <ref> we have a one-to-one correspondence between the matrices B__i's and the points of (_n,d). Thanks to the 𝔅_∘ construction, we have a one-to-one correspondence between the matrices 𝔅_∘∈ (_2^d)^n× n having the above characteristics (I), (II), (III) and the groups T_∘ with U(T_∘) generated by
_n+1,…,_n+d. 
That is, defining 
    _n,d={𝔅_∘∈ (_2^d)^n × n|𝔅_∘ satisfies conditions (I), (II), and (III)}

we have |_n,d|=|(_n,d)|. Thus, we aim to estimate |_n,d|.


We recall the following result given in <cit.>.

Let q be a power of 2. The number of n × n symmetric invertible matrices over _q with zero diagonal is

    q^n2∏_j=1^⌈n-1/2⌉( 1 - q^1 - 2j)     if n is even
     
    0    if n is odd
    .





Let N = n + d and V = (𝔽_2)^N, with n ≥ 2 and d ≥ 1. Let q = 2^d. Then we can define a lower bound ν (n,d) ≤ |_n,d| by


    ν(n,d) =  q^n2∏_j=1^⌈n-1/2⌉( 1 - q^1 - 2j)     if n is  even
     
    (q^n-1-2^n-1) q^n-12∏_j=1^⌈n-2/2⌉( 1 - q^1 - 2j)     if n is  odd



We require that 𝔅_∘ is full rank over _2, thus if it is invertible this condition is satisfied. Then the value given in Proposition <ref> is a lower bound on the number of all acceptable matrices 𝔅_∘. However, if n is odd from Proposition <ref> we would have only 0 as lower bound.

To tackle the n-odd case, we want to reduce it to the n-even case. We show how it is possible to construct a matrix 𝔅_∘ for fixed values n and d starting from a given 𝔅_∘' defined for values n'=n-1,  where n-1 is even, and d'=d.
Indeed, let 𝔅_∘'∈ (_2^d)^n-1 × n-1 be such that it is full rank over _2, symmetric and zero-diagonal. We need to construct the first row (the first column is the transpose of this) of 𝔅_∘, setting all the others equal to the rows of 𝔅'_∘. 
That is, 

    𝔅_∘=[[    0     ;   ^⊺ 𝔅_∘' ]].

Then, we need to verify how many possible 𝔅_∘ we can construct starting from 𝔅_∘', or equivalently how many vectors ∈ (_2^d)^n-1 we can use, in order to enforce 𝔅_∘∈_n,d.

As 𝔅_∘' is full rank over _2, summing the rows of this matrix we can create 2^n-1-1 non-zero vectors. Thus, we can choose 2^d(n-1)-2^n-1 different vectors  of (_2^d)^n-1 to construct 𝔅_∘. Hence, for any n we have (2^d(n-1)-2^n-1)|_n-1,d|≤|_n,d| and, in particular, for n odd we have at least (2^d(n-1)-2^n-1) ν(n-1,d) possible matrices 𝔅_∘.


Let N = n + d and V = (𝔽_2)^N. Then

    |ℳ_n,d|  = 
    2^d - 1 						   if  n = 2
    
    (2^d + 3)(2^d - 1)(2^d - 2) 				   if n = 3
    
    2^n2∏_j=1^⌈n-1/2⌉( 1 - 2^1 - 2j) 		   if d = 1 and n is even
    
    0 		   if d = 1 and n is odd



The cases n=2 and n=3 were already proved in <cit.>. We restate here the proof using symmetric matrices, obtaining a shorter and clearer proof.

If n=2 then

    𝔅_∘ = [ 0  ;   0 ]

 with ∈𝔽_2^d. Of course the only vector that we have to avoid is the zero vector. Thus we can use 2^d-1 vectors  to construct 𝔅_∘.

If n=3 then

    𝔅_∘ = [ 0    ;   0  ;     0 ]

with ,,∈𝔽_2^d such that 𝔅_∘∈_n,d.

 We need to find all the triples (,,) such that the matrix 𝔅_∘ is full rank over _2, that is, summing any rows of it we do not obtain the zero vector. Let us consider the different cases:

	
  * ≠ 0 : 2^d - 1 possible values for ,
	
		
  * = 0 : so ∉{ 0,} and so we get 2^d - 2 possible values
		
  * = : so ∉{ 0,} and so we get 2^d - 2 possible values
		
  * ≠ : so  can be any element, ∉{ 0,}. So 2^d(2^d-2) possible pairs (,).
	
	
  * = 0 : we have ≠ 0 and z ∉{ 0,y } and so we get (2^d-1)(2^d-2) possible pairs (,).


Summing all the possible triple (,,), we get

    (2^d - 1)(2^d - 2 + 2^d - 2 + 2^d (2^d -2)) + (2^d -1)(2^d - 2) = (2^d-1)(2^d-2)(2^d + 3)




Now, let n≥ 2 and fix d=1. As we consider 𝔽_2^d = 𝔽_2, we have that _n,d is the set of symmetric matrices having all zeros on the diagonal and invertible. From Proposition <ref> we have our claim.


Let us compare the upper bound and the lower bound on the cardinality of _n,d. 
We recall a theorem on the infinite product convergence criteria, corollary of the monotone convergence theorem (more details can be found in <cit.>).
­

Let {a_j}_j∈ℕ⊆ℝ_+. Then
∏_j=1^∞ a_j converges if and only if ∑_j=1^∞ln (a_j) converges.

Moreover, assume a_j ≥ 1, and denote  a_j = 1 + p_j. Then

    1 + ∑_j=1^∞ p_j≤∏_j=1^∞ (1 + p_j) ≤ e^∑_j=1^∞ p_j,

that is, the infinite product converges if and only if the infinite sum of the p_j converges.



Let μ(n,d) be the bound given in Proposition <ref> and let ν(n,d) be the bound given in Proposition <ref>. Let q = 2^d and d≥ 2. If n is even, then

    μ(n,d)/ν(n,d)≤∏_j=1^∞1/(1-q^1-2j)≤ e^q+1/q(q-1)

 if n is odd, then 

    μ(n,d)/ν(n,d)≤2∏_j=1^∞1/(1-q^1-2j)≤ 2 e^q+1/q(q-1).



We have

    μ(n,d)=   q^n2-1-∑_r=1^n-2n r(q-1)^n-r2
    ≤   q^n2.

Consider the case n even

    μ(n,d)/ν(n,d)   ≤q^n2/q^n2∏_j=1^⌈n-1/2⌉( 1 - q^1 - 2j)
       = ∏_j=1^⌈n-1/2⌉1/( 1 - q^1 - 2j)
       ≤∏_j=1^∞1/( 1 - q^1 - 2j),

since we can write

    1/1-q^1-2j = q^2j-1/q^2j-1-1 = 1 + q/q^2j - q.

Defining 

    p_j := q/q^2j - q

we trivially have that p_n ≥ 0 and


    1 + ∑_j=1^∞ p_j ≤∏_j=1^∞1/(1-q^1-2j)≤ e^∑_j=1^∞ p_j.


We have for any j ≥ 2

    p_j ≤1/q^j.

From this, we get

    ∑_i=1^∞ p_j ≤ p_1+∑_i=2^∞1/q^j= 2/q-1-1/q=q+1/q(q-1)

and so

    ∏_j=1^∞1/(1-q^1-2j)≤ e^q+1/q(q-1).


Now let n be odd,

    μ(n,d)/ν(n,d)   ≤q^n2/(q^n-1-2^n-1)· q^n-12∏_j=1^⌈n-2/2⌉( 1 - q^1 - 2j).

Since ji=j-1i-1+j-1i, n≥ 2 and d≥ 2  we have

    μ(n,d)/ν(n,d)   ≤q^n-1/(q^n-1-2^n-1)·∏_j=1^⌈n-2/2⌉( 1 - q^1 - 2j)
        = 1/(1-2^n-1/q^n-1)·∏_j=1^⌈n-2/2⌉( 1 - q^1 - 2j)
       ≤1/(1-2^n-1/q^n-1)∏_j=1^∞1/( 1 - q^1 - 2j)
       ≤2∏_j=1^∞1/( 1 - q^1 - 2j)≤ 2 e^q+1/q(q-1).



Note that in Proposition <ref>, the comparison for the case d=1 is avoided as the lower bound is the exact value of |_n,d|.


For all possible values of n≥ 2 and d≥ 2 we have

    lim_n→∞μ(n,d)/ν(n,d)=∏_j=1^∞1/( 1 - q^1 - 2j)

and

    lim_d→∞μ(n,d)/ν(n,d)=1.



Consider the case n odd, then 

    μ(n,d)/ν(n,d)    = q^n2(1-1/q^n2-∑_r=1^n-2n r∏_i=1^n-r2(q-1)/q^n2)/(q^n-1-2^n-1)· q^n-12∏_j=1^⌈n-2/2⌉( 1 - q^1 - 2j)
        = (1-1/q^n2-∑_r=1^n-2n r∏_i=1^n-r2(q-1)/q^n2)/(1-2^n-1/q^n-1)·∏_j=1^⌈n-2/2⌉( 1 - q^1 - 2j)
       =(1-1/q^n2-∑_r=1^n-2n r∏_i=1^n-r2(q-1)/q^n2)/(1-2^n-1/q^n-1)∏_j=1^⌈n-2/2⌉1/( 1 - q^1 - 2j)

Consider 

    ∑_r=1^n-2n r∏_i=1^n-r2(q-1)/q^n2   =∑_r=1^n-2n r(q-1)^n-r2/q^n2
       ≤∑_r=1^n-2n rq^n-12-n2
       ≤2^n-2/q^n-1.

This implies that the limit of (<ref>), as n approaches infinity, is 0 and then the limit

    lim_n→∞q^n2(1-1/q^n2-∑_r=1^n-2n r∏_i=1^n-r2(q-1)/q^n2)/(q^n-1-2^n-1)· q^n-12∏_j=1^⌈n-2/2⌉( 1 - q^1 - 2j)=∏_j=1^∞1/( 1 - q^1 - 2j).


The case n even is similar.











Moreover, from the proof of Proposition <ref> we have

    1≤μ(n,d)/ν(n,d)≤
     e^q+1/q(q-1)    if n is even
    1/(1-2^n-1/q^n-1)e^q+1/q(q-1)    if n is odd

and immediately we have that 

    lim_d→∞μ(n,d)/ν(n,d)=1.


 
From the results obtained in this section we can see that if we would tackle Problem 3. given in Section 2, then it is not possible to search among all the possible practical hidden sums of a given space V. Indeed, it will be computationally hard, given the huge amount of these operations, also in small dimensions.




§ ON HIDDEN SUMS FOR LINEAR MAPS

In this section we investigate Problem 3 given in Section 2 page prob3. In particular we want to see if, for a given ∈(V,+), it is possible to individuate an alternative sum ∘ such that ∈(V,∘).

Let T_∘⊆(V,+) and ∈(V,+)∩(V,∘) then U(T_∘) is invariant under the action of , i.e. U(T_∘)=U(T_∘).


Recall that  is linear with respect to both + and ∘. Let ∈ U(T_∘),  and so ∘=+ for any . Thus, for all  we have

    ∘=^-1∘=(^-1∘)=(^-1+ )=+ .

That implies ∈ U(T_∘), and so U(T_∘)⊆ U(T_∘).



Let T_∘⊆(V,+) and ∈(V,+). Then  is in (V,+)∩(V,∘) if and only if for all ∈ V we have

    _=_,

where _=__.


Let  be fixed. Then for all  we have

    (∘)λ = λ∘λ

	where
	
    (∘)λ   = (_ + )λ
       = _λ + λ

	and 
	
    λ∘λ   = λ_λ + λ .

	Imposing the equality we get

    ( _λ) = λ_λ.

Vice versa let ,∈ V 

    (∘)   =_+
       =_+
       =∘.






Now we will characterize the linear maps which are also linear for an operation ∘, such that U(T_∘) is generated by the last elements of the canonical basis.

Let V=(_2)^N, with N=n+d, n≥ 2 and d≥ 1. Let T_∘⊆(V,+) with U(T_∘)={_n+1,...,_n+d}. Let ∈(V,+). Then ∈(V,+)∩(V,∘) if and only if

    =[[ Λ_1 Λ_2;   0 Λ_3 ]],

with Λ_1∈((_2)^n), Λ_3∈((_2)^d), Λ_2 any matrix  in (_2)^n× d and for all ∈ V B_Λ_3=Λ_1B_ (see Theorem <ref> for the notation of B_). 


Let 

    =[[ Λ_1 Λ_2; Λ_4 Λ_3 ]],

Λ_1∈ (_2)^n× n, Λ_3∈ (_2)^d× d, Λ_2∈ (_2)^n× d and Λ_4∈ (_2)^d× n

From Proposition <ref> we have that Λ_4=0 as U(T_∘) is -invariant. Thus, as  is invertible Λ_1∈((_2)^n) and Λ_3∈((_2)^d).

By standard matrix multiplication it can be verified that (<ref>) and B_Λ_3=Λ_1B_ are equivalent. Then, we need to show that this condition does not depend on the matrix Λ_2. Indeed, let =(x_1,...,x_n,x_n+1,...,x_n+d)∈ V, and define =(x_1,...,x_n) and '=(x_n+1,...,x_n+d), i.e. =(,'). As reported in Section 3 page  condizionei, we have _=_(,0), which implies B_=B_(,0), for all ∈ V.
Then, B_Λ_3=Λ_1B_ for all ∈ V if and only if B_(,0)Λ_3=Λ_1B_(Λ_1,0) for all =(x_1,...,x_n).
So we have 

    [[ Λ_1 Λ_2;   0 Λ_3 ]]∈(V,∘),

for any Λ_2.


In the following, as Λ_2 in Proposition <ref> could be any matrix, we will consider linear maps of type

    [[ Λ_1   *;   0 Λ_3 ]]∈(V,∘),

with Λ_1∈((_2)^n), Λ_3∈((_2)^d) and * denotes for any matrix of size n× d.



From the propositions above, if we want to find an operation ∘ that linearizes a linear map ∈(V,+), i.e. we want to enforce

    [[ Λ_1   *;   0 Λ_3 ]]∈(V,∘),

then we have to construct some matrices B_'s such that B_Λ_3=Λ_1B_ for all . Moreover, as the standard vectors _i's form a basis for the operation ∘, then we need to individuate only the matrices B__i, so that B__iΛ_ 3=Λ_1B__i, and in particular that

    B__iΛ_ 3=Λ_1B__i=Λ_1(∑_i=1^nc_iB__i),

where c_1,…,c_n are the first components of the vector _i.















 



Correctness of Algorithm <ref>:

Note that thanks to the form of the maps __i given in Theorem <ref>, we always have __i^2=1_V, whatever the matrix B__i is. This property, with condition 3 in the algorithm, implies __i^2=1_V, so T_∘=⟨__1,...,__n+d⟩ is elementary.

 Condition 4 guarantees that T_∘ is abelian. Then, T_∘ is also regular (see Corollary 3.8 in <cit.> for more details).
This implies that T_∘=⟨__1,...,__n+d⟩ is a practical hidden sum.

The first condition, as seen in Proposition <ref>, is equivalent to having __i=__i for all _i, and for Remark <ref>, we have also _=_ for any . Then, from Proposition <ref> we have ∈(V,∘). To conclude, condition 2 implies that U(T_∘) contains _n+1,...,_n+d.

Viceversa, consider T_∘ a practical hidden sums (with __i as in (<ref>)) such that:


  * T_∘⊆(V,+), T_+⊆(V,∘),

  * U(T_∘) contains _n+1,...,_n+d,

  * ∈(V,∘).

 We need to check that T_∘ is an output of the algorithm. Equivalently, we need to check that the matrices B__i associated to this group satisfies the condition of the system in Algorithm <ref>.

Since T_∘ is elementary and abelian, conditions 3 and 4 are satisfied. Also, condition 2 holds because U(T_∘) contains _n+1,...,_n+d. For the first condition, since ∈(V,∘) we have _=_ for any , which is equivalent to B_Λ_3=Λ_1B_ for all , and in particular for all _i.



Note that, from Algorithm <ref> we obtain operations ∘ such that 
{_n+1,…_n+d}⊆ U(T_∘). Indeed, we required that for n+1≤ i≤ n+d, B__i =0, but we did not require that the combinations of B__1,...,B__n are non-zero. So, if we want to construct hidden sums with (U(T_∘))=d, we just process the solution of Algorithm <ref> and discharge the 𝔅_∘'s such that rank__2(𝔅_∘)<n.






 §.§ Complexity of our search algorithm

To solve the linear system in our algorithm, we represent the matrices as vectors:


    [ b_1,1     ⋯ b_1,d;     ⋮     ⋱     ⋮; b_n,1     ⋯ b_n,d ]⟷[ 1-st rowb_1,1 , ... ,b_1,d , 2-nd rowb_2,1 ,... , b_2,d ,                                                       ...                             , n-th rowb_n,1 , ... , b_n,d ]




	
  * From i=1,...,n, ∑_j c_jΛ_1B__j =  B__iΛ_3 we have n^2  d linear equation in n^2  d variables.
	
  * From _i B__i = 0 and _i B__j = _j B__i we obtain n+12d linear equations, in the same variables.

So, we only need to find a solution of a binary linear system  of size 
    (n^2d + n+12d) · n^2d.




Therefore, we have immediately the following result


The time complexity of Algorithm <ref> is 𝒪( n^6 d^3 ) and the space complexity is 𝒪( l · 2^d-1 n^2  ) where l is the dimension of the solution subspace.























In Table <ref> we report some timings for different dimensions of the message space V, fixing the value of d equal to 2. 











§ HIDDEN SUMS FOR PRESENT'S MIXING LAYER















Here we report our results on the search for a hidden sum suitable for the mixing layer of PRESENT, _P, which is  defined by the permutation reported in Table <ref>.




Algorithm <ref> requires in input a linear function in the block form:

    λ' = (Λ_1     * 
     0    Λ_3 )

with Λ_1∈((_2)^n) and Λ_3∈((_2)^d) for some integers n and d.


Note that a matrix as in (<ref>) is such that the space U'={_n+1,…,_n+d} is λ'-invariant. So, in order to transform a mixing layer  into one as in (<ref>), it is necessary to individuate a subspace U such that U=U. Then, by conjugating  by a linear map π such that Uπ={_n+1,…,_n+d}, we will have πλπ^-1 as in (<ref>). From a group T_∘ obtained from Algorithm <ref> for the map πλπ^-1 we will obtain a hidden sum for , that is, π^-1 T_∘π.

For this reason we consider the matrix given by the permutation

    π_P = (1 , 61)(22, 62)(43,63) ∈({ i | i = 1,...,64 })

so that

    π_P λ_P π_P^-1 = (Λ_1     0 
     0     I_4) = λ̂_P

We can now apply Algorithm <ref> and obtain all the possible operations that linearize λ̂_P. The operation space will be denoted by O.

The time required to compute the operation space O is ∼ 10.420 seconds and it is generated by 2360 60-tuples of 60× 4 matrices. So the number of operations that linearize λ̂_P, in the form described in Theorem <ref>, is | O| = 2^2360.



We take a random operation ∘ (Table <ref>) obtained by our algorithm. The operation has rank__2(𝔅_∘) = 60 = n and so the operation is such that (U(T_∘)) = 4 = d. To compress the table, we represent every row of B_e_i as a number in {0,...,(2^4 -1)}, and, as we did in Remark <ref>,  row i represents the matrix B__i.





§ CONCLUSIONS

Continuing the study of <cit.>, here we focused on the class of hidden sums such that T_∘⊆(V,+) and T_+⊆(V,∘), which we called practical hidden sums, as these could be used to exploit new attacks on block ciphers.

We gave a lower bound on the number of the practical hidden sums. Then we compared this lower bound with the upper bound given in <cit.>.

In the second part, we dealt with the problem of individuating possible practical hidden sums for a given linear map, providing Algorithm <ref> and showing an example on the case of the PRESENT's mixing layer.

A dual approach is under investigation in <cit.> (some of the results are reported in <cit.>), where the author takes into consideration some S-boxes, which would be strong according to classical cryptanalysis, and identify
some practical hidden sums that weaken significantly the non-linearity properties of the S-Boxes. Once the candidate hidden sums have been found, some (linear) mixing layers are constructed such that they are linear with respect to a hidden sum and the resulting cipher turns out to be attackable by the  clever attacker.


§ ACKNOWLEDGEMENTS


The authors would like to thank the anonymous referees for their stimulating suggestions, and several people for interesting discussions: R. Civino and R. Aragona.

Part of the results in this paper are from the first's author Master thesis, supervised by the last author. They have been presented partially at WCC 2017.

This research was partially funded by the Italian Ministry of Education, Universities and Research, with the project PRIN 2015TW9LSR  “Group theory and applications”.





10
url<#>1urlprefixURL href#1#2#2 #1#1

calderini2017elementary
M. Calderini, M. Sala, Elementary abelian regular subgroups as hidden sums for
  cryptographic trapdoors, arXiv preprint arXiv:1702.00581.

CGC-cry-art-Bogdanov2007
A. Bogdanov, L. R. Knudsen, G. Leander, C. Paar, A. Poschmann, M. Robshaw,
  Y. Seurin, C. Vikkelsoe, PRESENT: An Ultra-Lightweight Block Cipher, in:
  Proc. of CHES 2007, Vol. 7427 of LNCS, Springe, pp. 450–466r, 2007.

CGC-cry-book-stin95
D. Stinson, Cryptography, Theory and Practice, CRC Press, 1995.

CGC-cry-book-daemen2002design
J. Daemen, V. Rijmen, The design of Rijndael, Information Security and
  Cryptography, Springer-Verlag, Berlin, 2002, AES - the Advanced
  Encryption Standard.

CGC-cry-art-carantisalaImp
A. Caranti, F. Dalla Volta, M. Sala, On some block ciphers and imprimitive
  groups, AAECC 20 (5-6), pp. 229–350, 2009.

daemen2002design
J. Daemen, V. Rijmen, The design of Rijndael: AES-the advanced encryption
  standard, Springer Science & Business Media, 2002.

CGC-cry-art-serpent
R. Anderson, E. Biham, L. Knudsen, SERPENT: A New Block Cipher Proposal,
  in: Fast Software Encryption, Vol. 1372 of LNCS, Springer, pp.
  222–238, 1998.
filion A. Bannier and E. Filiol, Partition-based trapdoor ciphers. In: Partition-based Trapdoor Ciphers. InTech, 2017
CGC-cry-art-paterson1
K. G. Paterson, Imprimitive permutation groups and trapdoors in interated
  block ciphers, in: Fast software encryption, Vol. 1636 of LNCS,
  Springer, Berlin, pp. 201–214, 1999.

CGC-cry-art-sparr08 R. Sparr and R. Wernsdorf, Group theoretic properties of Rijndael-like ciphers, Discrete Appl. Math., 156, pp. 3139–3149, 2008

CGC-cry-art-Wern2 R. Wernsdorf, The one-round functions of the DES generate the alternating group. In: Eurocrypt. 1992. pp. 99-112.




court N. Courtois,
The Inverse S-box, Non-linear Polynomial Relations and Cryptanalysis of Block Ciphers, in: AES 4 Conference, Bonn May 10-12, vol. 3373 of LNCS, Springer, pp. 170-188, 2004.



Rob
C. Blondeau, R. Civino and M. Sala, Differential Attacks: Using Alternative Operations, Des. Codes Cryptogr., pp.1-23, 2018.
Rob2R. Civino, Differential attacks using alternative operations and block
cipher design. Ph.D. thesis, University of Trento (2018).

macwilliams69ort
J. MacWilliams, http://www.jstor.org/stable/2317262Orthogonal matrices
  over finite fields, The American Mathematical Monthly 76 (2) (1969)
  152–164.
<http://www.jstor.org/stable/2317262>


stewart2015calculus
J. Stewart, Calculus, Cengage Learning, 2015. ]