(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)
(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.
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.
How should Alice's mailer handle the processing of the return
address information?
When Bob receives the reply, what does it contain? How can he
obtain the cleartext reply?
(text, problem 14.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)
(20 points) Let L = (S_{L}, ≤_{L}) be a lattice. Define:
Prove that the structure IL = (S_{L}, ≤_{IL}) is a lattice.
(text, problem 16.2, modified)
Extra Credit
(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)