Homework #4

Questions

1. (25 points) Suppose the composite machine catdog (see Section 8.4.1) emits the same value from the left and the right. Show that it has received an even number of inputs from the left. (text, problem 8.7 modified)
2. (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)
3. (25 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(y_s | x_t), H(y_s), H(z_s | x_s), and H(z_s) and showing that H(y_s | x_s) ≤ H(y_s) and H(z_s | x_s) ≤ H(z_s)$ (text, problem 16.1)
4. (20 points) Let L = (S_L, ≤_L) be a lattice. Define:
   1. S_IL = { [a, b] | a, b ∈ S_L ∧ a ≤_L b }
   2. ≤_IL = { ([a₁, b₁], [a₂, b₂]) | a₁ ≤_L a₂ ∧ b₁ ≤_L b₂ }
   3. lub_IL([a₁, b₁], [a₂, b₂]) = (lub_L(a₁, a₂), lub_L(b₁, b₂))
   4. glb_IL([₁, b₁, [a₂, b₂]) = (glb_L(a₁, a₂), glb_L(b₁, b₂))
   Prove that the structure IL = (S_L, ≤_IL) is a lattice. (text, problem 16.2, modified)

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)

ECS 235B, Foundations of Computer and Information Security Winter Quarter 2012