The image below shows Adobe Acrobat’s conversion to Microsoft Powerpoint of a typical slide produced by LaTeX and Beamer. The original is shown below.
For the £70 annual fee Adobe charge for turning on this misfeature, I think one might expect something better. The execrable kerning is just one final kick in the teeth. Fortunately for my credit card, I was able to brandish the Consumer Contracts Regulations in an online chat and have been promised a full refund. I’ve seen similar glitches in journal papers: the culprit now seems clear. As an alternative on the Mac, I suggest using pdf-to-keynote and then exporting from Keynote. Or better still, have nothing to do with either Adobe or Microsoft — if only that were feasible. In fairness, I should note that the output from Adobes’s conversion is editable in Microsoft Powerpoint; unfortunately the only reasonable edit one could make it to delete the lot and start over.
Posted by mwildon 
defined by identifying 
with the finite field 
and then inverting non-zero elements. (The zero word is the unique fixed point of 
.) In a typical round the input in 
is split into 
bytes and the non-linear function 
-affine permutations, and these are followed by a final key addition in 
and encryption functions defined by 
. For each guessed first key 
there is a unique 
such that 
, namely 
reveal. To save space, write 
for 
. Suppose that 
is a possible key:
:
, the output difference 
of the 
elements of 
. This is usually taken as a sign of the cryptographic strength of 
from 
and 
. For the toy cipher, this pair is 
, and so we determine 
, leaving exactly two possible keys. 
. If 
then the equation 
has exactly zero or two solutions. 
then 
and so 
and 
. Now 
if and only if 
. This is a quadratic equation in 
not having a repeated root. 
.
, there are four solutions, namely 
, 
, and the two roots of 
lying in 
. In fact, since 
has 
roots if and only if 
, which is a co-dimension 
for each non-zero input difference 
, each except 
arising from exactly two inputs 
, corresponding to 
, and omitting the parenthetical paragraph entirely. Still I’m fairly sure no-one except the keenest M.Sc. students got the idea. Probably I will scrap it next year, and instead give an example from a different toy block cipher with a more easily defined 
-box. Or maybe, since there is no chance of universal comprehension, I should just leave it to a problem sheet, with a hint that the lemma above follows from 
is annoying. It arises because 
has a root in 
with 
odd, there are 
output differences for any input difference 
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 
; these are the (no-longer-so) exceptional 
, and the reciprocals of the non-zero elements in the subspace
for 
. Quadratic equations are now more easily understood: we can just complete the square to see that exactly 
of the elements 
are output differences; again the output difference 
might give a nice example, using the function 
such that 
and 
. This function is weak respect to the input difference of 
for any 
. Perhaps surprisingly, this makes 
. But because of the identity
. One could replace the one-time-pad key addition in my toy block cipher with 
and run essentially the same attack, but as a direct replacement for pseudo-inverse, squaring has completely the wrong properties.
, working in 
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 
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 
doubles 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 
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 
, it seems reasonable to assume that the cost of 
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 define 
by 
. (This is multiplication in the finite field: we will ignore that the encryption functions 
are not injective.) Define 
by 
. The set 
of keys that meet-in-the-middle at 
is 
. Hence 
, so we need 
large compared to 
. In this case the chance is 
that the true key is found, but since the second components of each half of the encryption key are irrelevant, this will not worry the attacker. One reason for not using 
is that the composed encryption functions for keys 
are then the same whenever 
, giving a further collapse. For the composed cipher as defined, since the affine group on 
is sharply 
.
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 
.
