# 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: