Given a function, F, our goal is to efficiently distinguish whether F
is E or a random function by making queries to F.

1. Insecure.  

   distinguish_E1_from_R(F)
     x = random();
     y = F(x);
     z = F(y);
     if (z == x)
       return "E1";
     else
       return "random";

This works because E(k,E(k,x)) = (x xor k) xor k = x, but a random
function only has a 2^-n chance of this happening.

2. Secure.  Here's a proof, although you did not need to give this in
your homework.

Suppose we had a distinguish_E2_from_R() function that could
distinguish E from a random function.  Then we can create a new
function that can distinguish AES from R as follows

   distinguish_AES_from_R(F)
     define G(x) = F(x) xor 11...1;
     if (distinguish_E2_from_R(G) == "E2")
       return "AES";
     else
       return "random";

If we pass AES(k,x) into distinguish_AES_from_R(), then it will set
G=E2, and hence distinguish_E2_from_R(G) will return "E2", and hence
we will return "AES".  If F is a random function, then G is also a
random function(see note), so distinguish_E2_from_R(G) will return
random.  Since we assume that no distinguisher for AES exists, there
must not be a distinguisher for E2.

Note: F is a random function if it is drawn uniformly at random from
all functions.  The transformation F |---> G is injective, so G is also
chosen uniformly at random if F is.

3. Insecure.  Since the attacker knows the key, he can just compute
   AES(00...0, x) and see if he gets the same result as from F, i.e.

   distinguish_E3_from_R(F)
     x = random();
     y = F(x);
     z = AES(00..0,x);
     if (y == x)
       return "E3";
     else
       return "random";

4. Insecure.  We can build a distinguisher in many ways.  Here's a
   simple one.

   distinguish_E4_from_R(F)
     x = random();
     y = F(x);
     z = AES^-1(00...0,y);
     w = F(z);
     u = AES^-1(00...0,w);
     if (z == x)
       return "E4";
     else
       return "random";
     
This works because, if F == E4, then

z = AES^-1(0,F(x)) = AES^-1(0,AES(0,x) xor k) = x xor k
Similarly, u = z xor k, but z xor k = (x xor k) xor k = x.

A random function is extremely unlikely to have this property.

5. Secure.  Suppose we had a distinguisher for E5.  Then we could
   build a distinguisher for AES as follows:

   distinguish_AES_from_R(F)
     k1 = random();
     define G(x) = AES(k1, F(x));
     if (distinguish_E5_from_R(G) == "E5")
       return "AES";
     else
       return "random";

Obviously, if F == AES, then G == E.  Also, as in part two, if F is
chosen at random, then G is also chosen at random, so
distinguish_E5_from_R will return "random".

6. Insecure.  You can distinguish this from a random function by
   querying it on two different inputs that only differ on one half,
   i.e.

   distinguish_E6_from_R(F)
     x1 = random();
     x2 = random();
     x3 = random();
     (y1, y2) = F((x1, x2));
     (z1, z2) = F((x1, x3));
     if (y1 == z1)
       return "E6";
     else
       return "random";

7. Insecure.  Observe that E(k,E(k,x)) == x, so we can use the
   same distinguisher as from part 1.