Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
When I am studying about linear cryptanalysis, I have a question about correlation of linear trail.
Let $U=(u_0, u_1 , ...,u_n)$ be a linear trail
Then we can compute a correlaton of linear trail $U$ such that $C_{U}=\prod_{i}C^{r_i}_{u_{i}u_{i-1}} $
where $C^{r_i}_{u_{i}u_{i-1}}$ is a correlation of $r_i $th round.
My question is why we compute correlation of linear trail by producting round correlation?
Is there any mathematical proof of this point?
Thank you.
This is due to the modelling approach called Markov Ciphers, by Jim Massey (I think).
Basically the hypothesis is that round by round independence applies and correlations can be concatenated by using conditional probabilities and multiplying the probabilities. Since you must have the previous and current round correlations to build up a trail step by step, you apply conditional probability.
Daemen and Rijmen (designers of AES) state:
The Markov cipher theory [18] has inspired many research on iterative block ciphers, including ours. It can be considered as the first approach to design block ciphers resistant against differential cryptanalysis. A Markov cipher is an (iterative) cipher for which the average difference propagation probability over one round is independent of the round’s text input. For such ciphers, the assumption of independent round keys allows to compute the average DP of a characteristic as the product of the probabilities of the individual round. Here the average is taken over all the round keys, considered as independent variables. The average DP of a differential can be computed —in principle— as the sum of the probabilities of all characteristics with input difference a in the first round, and output difference b in the last round. Estimating the average probability of a differential to be equal to the fixedkey probability for almost all keys, is called making the hypothesis of stochastic equivalence. After the publication of linear cryptanalysis, Markov cipher theory has been extended to the resistance against linear cryptanalysis (e.g. see [26, 30]), leading to analogous conclusions for the LP of linear approximations (hulls) over the cipher. In [27] Markov theory was used to show that the average DP values in a Markov cipher employing differentially 2-uniform mappings converges exponentially fast to a flat distribution with high probability.
The quote above is from their paper https://eprint.iacr.org/2005/212.pdf
