As a toy model for a difference attack in my Cipher Systems course, I used the block cipher with plaintext and ciphertexts 
where 
Suppose you know a single plaintext/ciphertext pair 
Thus a single known plaintext/ciphertext pair does not reveal either component of the key. To motivate the attack in this post, let us consider what two pairs 
A little thought shows that another possible key is 
Observe that the differences of top and bottom are in both cases
This illustrates the critical point that differences are invariant under key addition, but typically changed by non-linear functions such as 
can be 
Differences through pseudo-inverse.
Lemma. Let 
Proof. If 
We may therefore assume that 
(In the exceptional case 
In my course I spent an entire lecture on the difference attack, simplifying the lemma by only considering 
Variations on pseudo-inverse
is annoying. It arises because 
has a root in . Over any 
with 
odd, there are 
output differences for any input difference . For instance, over 
we only see the exceptional case (and even more embarrassingly, the pseudo-inverse function 
is linear), while over 
, defined by 
, the output differences for input difference are 
; these are the (no-longer-so) exceptional 
, and the reciprocals of the non-zero elements in the subspace
with 
for an odd prime. Taking the input difference , now applied (and extracted) using arithmetic in , we have
for 
might give a nice example, using the function 
such that 
and 
. This function is weak respect to the input difference of , since, by definition, 
for any 
. Perhaps surprisingly, this makes less suitable for the attack. The situation for even input differences is somewhat messy. Clearly this is a non-starter for my course.
in . We have
so as seen above, there is a affine codimension
Posted by mwildon 
of 
, let 
denote the irreducible character of the symmetric group 
canonically labelled by the partition 
is the trivial character, 
is the sign character, and 
is the irreducible 
-degree constituent of the natural permutation character 
. Thus 
and 
for 
. Let 
be the sum of all the characters labelled by hook partitions. Let 
be the set of permutations in 
is the number of cycles in 
.
denote the 
th exterior power of a character or representation. Let 
be a complex representation of a finite group 
with character 
and let 
have eigenvalues 
in its action on 
. Let 
be a basis for 
-th elementary symmetric polynomial evaluated at the eigenvalues 
be the natural representation of 
is the sign representation of 
. More generally, 
is the monomial representation of 
. Its character is known to be
. This decomposition is an immediate corollary of either the Young or Pieri rules. It may also be proved using Specht modules and an explicit isomorphism 
: see for instance 
in 
is odd, and 
, where the sum is over all 
cycles of length 
. The eigenvalues of the 
permutation matrix representing 
, where 
is a primitive 
, the generating function in (1) gives
. We now have
for all 
where the sum is over all 
not congruent to 
. Then by (2), 
, and the proof above suggests that 
may also have a fairly simple form. One might also look for analogous identities replacing 
. 
be the algebraic closure of 
and let 
be the natural representation of 
.
is an irreducible representation of 
is self-dual.
is self-dual.
is self-dual, reducible and semisimple.
, Springer Lecture Notes in Mathematics 830. These 
. Let 
for 
be 
commuting indeterminates and let ![K[x_{ij}]](https://s0.wp.com/latex.php?latex=K%5Bx_%7Bij%7D%5D&bg=ffffff&fg=333333&s=0 "K[x_{ij}]")
be the polynomial ring they generate. Given ![f \in K[x_{ij}]](https://s0.wp.com/latex.php?latex=f+%5Cin+K%5Bx_%7Bij%7D%5D&bg=ffffff&fg=333333&s=0 "f \in K[x_{ij}]")
and a 
matrix 
, let 
denote 
evaluated at the 
for 
of the general linear group is said to be polynomial of degree ![f_{IJ} \in K[x_{ij}]](https://s0.wp.com/latex.php?latex=f_%7BIJ%7D+%5Cin+K%5Bx_%7Bij%7D%5D&bg=ffffff&fg=333333&s=0 "f_{IJ} \in K[x_{ij}]")
for 
such that 
for all matrices 
-module 
and degree 
for 
. The symmetric power 
(defined as a quotient of 
) is a polynomial representation of degree 
then 
is the polynomial representation of degree 
. Hence 
, 
and 
. Note that since 
is a polynomial, of degree at most 
. Another difference between the infinite algebraic group 
arises when we define duality. 
to be the vector space dual 
with the action ![\rho^\star(X) \theta = [v \mapsto \theta(\rho(X^{-1}) v)].](https://s0.wp.com/latex.php?latex=%5Crho%5E%5Cstar%28X%29+%5Ctheta+%3D+%5Bv+%5Cmapsto+%5Ctheta%28%5Crho%28X%5E%7B-1%7D%29+v%29%5D.&bg=ffffff&fg=333333&s=0 "\rho^\star(X) \theta = [v \mapsto \theta(\rho(X^{-1}) v)].")
be a basis for 
. The calculation
, and so (carefully remembering the convention for matrices acting on column vectors), we have 
. The inverse and transpose combine to make this a well-defined representation, but except when 
, 
of 
denotes the determinant. The top-left coefficient is 
, and this is not a polynomial in 
. We shall see later that when this representation is restricted to the special linear group 
, duality is much better behaved.![\rho^\circ(X) \theta = [v \mapsto \theta(\rho(X^t)v)]](https://s0.wp.com/latex.php?latex=%5Crho%5E%5Ccirc%28X%29+%5Ctheta+%3D+%5Bv+%5Cmapsto+%5Ctheta%28%5Crho%28X%5Et%29v%29%5D&bg=ffffff&fg=333333&s=0 "\rho^\circ(X) \theta = [v \mapsto \theta(\rho(X^t)v)]")
and 
. A very similar calculation to the above shows that 
. Note that typically, the two transposes do not cancel. For instance,
and 
doubled and 
and 
halved.
, where 
. (The formal definition is below.) Indeed, with respect to the indicated basis of 
, the action is
. For instance, the first column is now given by the image of 
, namely
then 
, via the isomorphism defined by 
double the third column and halves the third row of a matrix 
, giving the matrix 
.) But if 
then the representations are non-isomorphic. Indeed, from the matrices above, it’s clear that 
as a subrepresentation, and not hard to see that in fact this is its unique non-trivial proper subrepresentation. The quotient is the one-dimensional determinant representation. (Some calculation is required: the warning example for 
has 
as its unique non-trivial proper subrepresentation. Thus, as expected from duality, the head of 
as a subrepresentation, where 
; since 
, 
it is a proper subrepresentation of 
then 
is spanned by 
and 
. (This indicates the general proof.)
. For this it is important to be clear on the definition of 
. We define it using the right action of the symmetric group 
by place permutation on 
in position 
on the left-hand side appears in position 
on the right-hand side.) 
. We call the elements of 
multi-indices. Given 
we define 
in the place permutation action. Then
. For instance if 
and 
of 
in 
are 
, 
and 
.
then 
is a different rearrangement of 
is the subspace of 
.
, where, as a standing convention, the sum is over all distinct rearrangements 
of 
. By Example 3 we have 
we see that the coefficient of 
.
. Given 
for 
denote the corresponding element of the dual basis of 
. We have![\rho_{(\mathrm{Sym}^r E)^\circ}(X) w_\mathbf{j}^\star = [w_\mathbf{i} \mapsto w_\mathbf{j}^\star \bigl( \rho_{\mathrm{Sym}^r V}(X^t) w_\mathbf{i}].](https://s0.wp.com/latex.php?latex=%5Crho_%7B%28%5Cmathrm%7BSym%7D%5Er+E%29%5E%5Ccirc%7D%28X%29+w_%5Cmathbf%7Bj%7D%5E%5Cstar+%3D+%5Bw_%5Cmathbf%7Bi%7D+%5Cmapsto+w_%5Cmathbf%7Bj%7D%5E%5Cstar+%5Cbigl%28+%5Crho_%7B%5Cmathrm%7BSym%7D%5Er+V%7D%28X%5Et%29+w_%5Cmathbf%7Bi%7D%5D.+&bg=ffffff&fg=333333&s=0 "\rho_{(\mathrm{Sym}^r E)^\circ}(X) w_\mathbf{j}^\star = [w_\mathbf{i} \mapsto w_\mathbf{j}^\star \bigl( \rho_{\mathrm{Sym}^r V}(X^t) w_\mathbf{i}].")
, the coefficient of 
is 
, this agrees with the coefficient of 
. Therefore the map 
defines a isomorphism of representations 
. 
. By Proposition 5, taking 
, there is a 
matrix 
. Hence, setting 
, we have
, while in the representation 
, the matrix representing 
. By the previous displayed equation, these representing matrices are conjugate by the fixed matrix 
. We first find the matrices for 
.
be the matrix representing 
where 
. Then
if the multi-index 
has two equal entries. (This holds even if 
be the subspace of 
for 
is a subrepresentation of 
.
. For a more conceptual proof of this, one could argue that since 
, of weight 
, it is irreducible; over any field the irreducible polynomial representations of 
for an isomorphism that holds after this restriction. Here it is in our running example.
. We saw in Example 1 that
then 
. Changing the basis of 
by swapping the first and second basis vectors and negating the third we get an isomorphic representation 
in which
. Therefore 
. 
.
. By the following calculation
and 
. Hence so are 
and 
, and since transposition preserves conjugacy, so are 
and 
. The proposition follows. 
, this isomorphism holds for arbitrary 
acting on a basis 
, the matrix 
representing 
with respect to the indicated basis is 
where 
, and setting 
and 
, we find that
. This isomorphism can be recast in various ways, for example, 
or 
.
. By Proposition 9 any isomorphism of 
-representations, provided we systematically replace contragredient duality 
with conventional duality 
. For instance, Example 10 implies that
. We have
-matrices are constantly 
we have
is reducible and semisimple, as claimed in the answer to the final quiz question.
be a representation of 
be the representation defined by 
invariant under 
for all 
. It follows that 
. The example 
and 
, has 
. It is also possible to have 
. For example, this is clearly the case if 
not contained in 
and 
of invertible functions 
indexed by keys 
. We say that the block cipher 
. For example, DES has 
and 
, while its successor AES has 
and 
(or 
or 
be block ciphers of block size 
, respectively. An easy way to boost the key length to 
, while keeping essentially the same cryptologics, is to compose the encryption functions from the two ciphers. Thus for 
we define
, this cryptoscheme offers only 
bits of security, rather than the expected 
quantities chosen or observed by the cryptanalyst. We cost by the number of encryption/decryption operations, or cryptops, justifying this assumption in the course of the argument.
be the (unknown) key. Let 
be a chosen plaintext and let 
be its observed encryption. (We write 
rather than 
to emphasise that in the chosen plaintext model, we can perform two-stage encryption using the unknown key pair 
the inverse of the encryption function 
. Let
, 
and 
cryptops are required to get this far. 
primitive operations for some smallish 
. Similarly 
is sorted using 
primitive operations. Working through the sorted lists we pair up the 
with the 
, for each 
. In one possible implementation this makes a list of pointers to the relevant members of 
. Since each cryptop for 
is those key pairs (for the composed cryptosystem) that meet-in-the-middle at 
. Fix 
using the guessed key pair 
, and check if
. If all 
. (But for simplicity, let’s say we carry on checking all the other keys.) The number of pairs to be checked in the final step is
cryptops. The total cost in cryptops is therefore 
.
is chosen uniformly and independently at random from the 
permutations of 
. We know that 
and for each other key 
that 
. Dually, we know that 
, and for each other key 
, the probability is 
. Therefore 
and 
are independently distributed as the shifted binomial distribution 
then 
and 
. (It is worth noting that 
and 
are not independent: for example we have 
where the union is disjoint, therefore 
.) It follows by linearity of expectation that ![\begin{aligned} \mathbb{E}[M] &= \mathbb{E}\bigl[\sum_{y \in \mathbb{F}_2^\ell} |\mathcal{K}_y| |\mathcal{K}'_y|\bigr] \\ &= \bigl( 1 + \frac{2^\ell-1}{2^n} \bigr)\bigl( 1 + \frac{2^{\ell'}-1}{2^n} \bigr) + (2^n-1) \bigl( \frac{2^\ell-1}{2^n} \bigr)\bigl( \frac{2^{\ell'}-1}{2^n} \bigr) \\ &= \frac{2^{\ell+\ell'}}{2^n} + 1 - \frac{1}{2^{n}} \end{aligned}](https://s0.wp.com/latex.php?latex=%5Cbegin%7Baligned%7D+%5Cmathbb%7BE%7D%5BM%5D+%26%3D+%5Cmathbb%7BE%7D%5Cbigl%5B%5Csum_%7By+%5Cin+%5Cmathbb%7BF%7D_2%5E%5Cell%7D+%7C%5Cmathcal%7BK%7D_y%7C+%7C%5Cmathcal%7BK%7D%27_y%7C%5Cbigr%5D+%5C%5C+%26%3D+%5Cbigl%28+1+%2B+%5Cfrac%7B2%5E%5Cell-1%7D%7B2%5En%7D+%5Cbigr%29%5Cbigl%28+1+%2B+%5Cfrac%7B2%5E%7B%5Cell%27%7D-1%7D%7B2%5En%7D+%5Cbigr%29+%2B+%282%5En-1%29+%5Cbigl%28+%5Cfrac%7B2%5E%5Cell-1%7D%7B2%5En%7D+%5Cbigr%29%5Cbigl%28+%5Cfrac%7B2%5E%7B%5Cell%27%7D-1%7D%7B2%5En%7D+%5Cbigr%29++%5C%5C+%26%3D+%5Cfrac%7B2%5E%7B%5Cell%2B%5Cell%27%7D%7D%7B2%5En%7D+%2B+1+-++%5Cfrac%7B1%7D%7B2%5E%7Bn%7D%7D+%5Cend%7Baligned%7D&bg=ffffff&fg=333333&s=0 "\begin{aligned} \mathbb{E}[M] &= \mathbb{E}\bigl[\sum_{y \in \mathbb{F}_2^\ell} |\mathcal{K}_y| |\mathcal{K}'_y|\bigr] \\ &= \bigl( 1 + \frac{2^\ell-1}{2^n} \bigr)\bigl( 1 + \frac{2^{\ell'}-1}{2^n} \bigr) + (2^n-1) \bigl( \frac{2^\ell-1}{2^n} \bigr)\bigl( \frac{2^{\ell'}-1}{2^n} \bigr) \\ &= \frac{2^{\ell+\ell'}}{2^n} + 1 - \frac{1}{2^{n}} \end{aligned}")
. Hence the total cost is estimated as
and 
are each permutations of 
. Thus for each chosen plaintext 
, the ciphertexts 
and 
are uniformly distributed on 
. The probability they agree is therefore 
. More generally, the probability that 
for all of the 
is 
key pairs, so the expected number of ‘false’ keys is very nearly ![\mathbb{E}\bigl[\frac{M}{2^{np}}\bigr]](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BE%7D%5Cbigl%5B%5Cfrac%7BM%7D%7B2%5E%7Bnp%7D%7D%5Cbigr%5D&bg=ffffff&fg=333333&s=0 "\mathbb{E}\bigl[\frac{M}{2^{np}}\bigr]")
; by the good approximation for 
. Setting 
, our estimate for the total work is then
is large compared to 
is very large then, as one would expect, then one can take 
: no checking cryptops are needed.
, so 
, 
and we need 
large compared to 
, the total work is 
. Clearly for any reasonable choice of 
cryptops. Even in 2009, using a 
, so 
and we need 
large compared to 
, the total work is 
, roughly balanced between the first and second phases. For AES with the longest key length, 
and 
and we need 
large compared to 
, the total work is 
. The second phase dominates. Of course neither attack is practical.
and let 
. Fix a commutative ring 
and distinct ideals 
, 
of 
. We suppose that 
is a 
-set then the composition 
is injective;
-set then the composition 
is surjective.
is surjective.
, pick 
such that 
mod 
. By hypothesis, for each 
such that 
, the unique element of 
for each 
is 
.
. Take ![R = \mathbb{F}_p[X]](https://s0.wp.com/latex.php?latex=R+%3D+%5Cmathbb%7BF%7D_p%5BX%5D&bg=ffffff&fg=333333&s=0 "R = \mathbb{F}_p[X]")
, 
, and 
and 
. (Thus the secret is 
, and the share for algebraist 
.) Property (1) holds because a polynomial of degree 
is uniquely determined by its values at the 
for 
, we have (2) in the strongest possible form.
(of which more later) and consecutive primes 
with 
. Let 
. Take 
, 
, 
and 
, we have (1). Suppose the 
algebraists numbered 
pool their shares. They can learn 
. Now 
‘candidate secrets’ of the form 
where 
. Provided 
.
vary by at most 
, and have mean size 
. Provided 
, 
, 
, 
and 
, 
, 
, 
. Thus 
. For the secret 
, lifting it to 
. If algebraists 
cooperate they can learn 
. This leaves 
and since 
, there are 
, 
, 
and 
). Choosing one of these at random gives them a 
chance of guessing the secret. 
and 
have size ![R = \mathbb{F}_p[X,Y]](https://s0.wp.com/latex.php?latex=R+%3D+%5Cmathbb%7BF%7D_p%5BX%2CY%5D&bg=ffffff&fg=333333&s=0 "R = \mathbb{F}_p[X,Y]")
. Fix 
and thresholds 
with 
and 
. Let 
with 
and 
. Fix distinct non-zero 
and distinct 
. The aim is to share a secret 
between teams 
where team 
consists of people 
. For this, choose 
such that 
. For each 
, let 
. For each 
, let 
. Issue 
as the share to person 
.
. By the linear isomorphism in the first example above, when 
itself. Suppose that 
. Then since 
. Given a 
-subset 
of ![h^\star \in \mathbb{F}[X]](https://s0.wp.com/latex.php?latex=h%5E%5Cstar+%5Cin+%5Cmathbb%7BF%7D%5BX%5D&bg=ffffff&fg=333333&s=0 "h^\star \in \mathbb{F}[X]")
, there is a unique polynomial 
with 
such that 
and 
for each 
. Explicitly,
; since 
takes each value in 
varies over the polynomials in ![\mathbb{F}_p[X]](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BF%7D_p%5BX%5D&bg=ffffff&fg=333333&s=0 "\mathbb{F}_p[X]")
of degree at most 
people in each team, each time using the normal Shamir Scheme.
acting on the 
, with coefficients in a field of characteristic 
and 
have order 
, and the reduction modulo 
-dimensional character induced from either of the two non-trivial linear characters of 
. (A short calculation with Mackey’s Formula and Frobenius Reciprocity shows the module is irreducible in characteristic zero; then since 
is odd, it reduces modulo 
and perform the analogue of the characteristic zero construction directly.) The permutation module for 
-submodule 
having either 
.
regarded as a permutation group acting on the 
. For 
, let 
, and let 
denote the line through 
. Let 
be the corresponding 
-permutation module.
, corresponding to the Möbius map 
and to the matrix 
in 
. The simple modules for 
correspond to the factors of 
is permuted by squaring, an idempotent killing the simple modules with minimal polynomial 
is 
. Therefore the module 
-dimensional module
is the sum of the first three basis vectors, so in its right action, 
is represented by
.
must appear in some vector in the 
where 
where 
for each 
and let 
and 
. The corresponding Möbius maps are 
and 
and one choice of corresponding matrices in 
and 
. Extending the calculation for 
.
be non-negative weights and let 
, 
be non-negative numbers such that 
. In particular, if 
then we obtain
