Exercises

2.1: Consider the following encryption scheme:

(a) Fill in the details of the Dec algorithm so that the scheme satisfies correctness.

(b) Prove that the scheme satisfies one-time secrecy.

2.2: In abstract algebra, a (finite) group is a finite set ? of items together with an operator ⊗ satisfying the following axioms:

• Closure: for all \(a, b \in ?\), we have \(a \oplus b \in ?\).
• Identity: there is a special identity element \(e \in ?\) that satisfies \(e \oplus a= a\) for all \(a \in ?\). We typically write “1” rather than e for the identity element.
• Associativity: for all \(a, b, c \in ?\), we have \((a \oplus b) \oplus c = a \oplus (b \oplus c)\).
• Inverses: for all \(a \in ?\), there exists an inverse element \(b \in ?\) such that \(a \oplus b = b \oplus a\) is the identity element of ?. We typically write “\(a^{−1}\)” for the inverse of a.

Define the following encryption scheme in terms of an arbitrary group (\(?,\oplus\)):

(a) Prove that \(\{0,1\}^{\lambda}\) is a group with respect to the XOR operator. What is the identity element, and what is the inverse of a value \(x \in \{0,1\}^{\lambda}\)?

(b) Fill in the details of the Dec algorithm and prove (using the group axioms) that the scheme satisfies correctness.

(c) Prove that the scheme satisfies one-time secrecy.

2.3: Show that the following encryption scheme does not have one-time secrecy, by constructing a program that distinguishes the two relevant libraries from the one-time secrecy definition.

2.4: Prove that if an encryption scheme \(\Sigma\) has \(|\Sigma.?| < |\Sigma.?|\) then it cannot satisfy one-time secrecy. Show an explicit attack.

2.5: Let \(\Sigma\) denote an encryption scheme where \(\Sigma.? = \Sigma.?\), and define \(\Sigma^2\) to be the following double-encryption scheme:

Prove that if \(\Sigma\) satisfies one-time secrecy, then so does \(\Sigma^2\).

2.6: Let \(\Sigma\) denote an encryption scheme and define \(\Sigma^2\) to be the following encrypt-twice scheme:

Prove that if \(\Sigma\) satisfies one-time secrecy, then so does \(\Sigma^2\).

2.7: Formally define a variant of the one-time secrecy definition in which the calling program can obtain two ciphertexts (on chosen plaintexts) encrypted under the same key. Call it two-time secrecy.

(a) Suppose someone tries to prove that one-time secrecy implies two-time secrecy. Show where the proof appears to break down.

(b) Describe an attack demonstrating that one-time pad does not satisfy your definition of two-time secrecy.

2.8: Show that the following libraries are interchangable:

Note that \(x\) and \(y\) are swapped in the first two lines, but not in the return statement.

2.9: In this problem we consider modifying one-time pad so that the key is not chosen uniformly. Let \(?^{\lambda}\) denote the probability distribution over \([0,1]^{\lambda}\) where we choose the \(i\)th bit to be 0 with probability 0.4 and 1 with probability 0.6.

Let \(\Sigma\) denote one-time pad encryption scheme but with the key sampled from distribution \(?^{\lambda}\) rather than uniformly in \(\{0,1\}^{\lambda}\).

Consider the case of \(\lambda = 5\). A calling program ? for the \(\mathscr{L}^{\Sigma}_{ots-^{\ast}}\) libraries calls QUERY(01011,10001) and receives the result 01101. What is the probability that this happens, assuming that ? is linked to \(\mathscr{L}_{ots-L}\)? What about when ? is linked to \(\mathscr{L}_{ots-R}\)?

2.10: During Alice’s role-playing campaign, it becomes necessary to roll an 8-sided die. Unfortunately, she has misplaced hers! Her only source of randomness is a coin. Help her out by showing that the following two libraries are interchangeable: