3. The boolean function $\oplus$ computes the exclusive-or of two boolean values: for v, w $\in$

{0, 1}, we have v $\oplus$ w = 1 if and only if v $eq$ w; otherwise, v $\oplus$ w = 0.

(a) Show that (x $\oplus$ v) $\oplus$ v = x for all x, v $\in$ {0, 1}.

(b) Let M be a string of length n over the alphabet {0, 1}, and let K be another string of the same length over the same alphabet. Let M $\oplus$ K be the string obtained by applying $\oplus$ one character or bit at a time to M and K.

(i) Compute M $\oplus$ K where M = 010001100011100 and K = 100110111101100.

(ii) Explain in what sense we may think of K as a key for encrypting messages.

(iii) How can you decrypt encrypted messages?

(iv) Could this idea be used for public-key encryption?

(v) What is your intuition about the "quality" of such a cryptographic scheme?

(c) (i) Discuss in what sense the public-key approach discussed here assumes that agents on a network trust each other. For example, think about the link between physical identities and their (alleged) public keys. Do your as-

sumptions depend on the agent's being human?

(ii) Can one eliminate entirely the need for trust in public-key cryptography schemes?

(iii) What infrastructures can you imagine that would manage and support trust of public keys on the Internet?