Homework #4

Due: May 24, 2013
Points: 100


  1. (30 points) Consider a scheme that allows a recipient to reply to a message from a chain of Cypherpunk remailers. Assume that encipherment is used throughout the chain.
    1. Bob selects a chain of remailers for the return path. He creates a set of keys and enciphers them so that only the key for the current remailer is visible to that remailer. Design a technique by which he could accomplish this. Describe how he would include this data in his message.
    2. How should Alice’s mailer handle the processing of the return address information?
    3. When Bob receives the reply, what does it contain? How can he obtain the cleartext reply?
    (text, problem 14.3)

  2. (30 points) Revisit the example for x := y + z in Section 16.1.1. Assume that x does not exist in state s. Confirm that information flows from y and z to x by computing H(ys | xt), H(ys), H(zs | xt), and H(zs) and showing that H(ys | xt) < H(ys) and H(zs | xt) < H(zs)
    (text, problem 16.1)

  3. (20 points) Let L = (SL, <L) be a lattice. Prove that the structure IL = (SIL, <IL) is a lattice, given the following definitions:
    1. SIL = { [a, b] | a, bSa <L b }
    2. <IL = { ([a1, b1], [a2, b2]) | a1 <L a2b1 <L b2 }
    3. lubIL([a1, b1], [a2, b2]) = (lubL(a1, a2), lubL(b1, b2))
    4. glbIL([a1, b1], [a2, b2]) = (glbL(a1, a2), glbL(b1, b2))
    (text, problem 16.2, modified)

  4. (20 points) Why can we omit the requirement lub(i, b[i]) < a[i] from the requirements for secure information flow in the example for iterative statements (see Section
    (text, problem 16.5)

Extra Credit

  1. (30 points) Prove that a system that meets the definition of generalized noninterference security also meets the definition of deducible security.
    (text, problem 8.6)

You can also obtain a PDF version of this. Version of May 12, 2013 at 10:38PM