2.6: Exercise
- Page ID
- 86423
Exercises
Below are two calling programs \(\mathcal{A}_{1}, \mathcal{A}_{2}\) and two libraries \(\mathcal{L}_{1}, \mathcal{L}_{2}\) with a common interface:
(c) What is \(\operatorname{Pr}\left[\mathcal{A}_{2} \diamond \mathcal{L}_{1} \Rightarrow\right.\) true \(] ?\)
(a) What is \(\operatorname{Pr}\left[\mathcal{A}_{1} \diamond \mathcal{L}_{1} \Rightarrow\right.\) true \(] ?\)
(b) What is \(\operatorname{Pr}\left[\mathcal{A}_{1} \diamond \mathcal{L}_{2} \Rightarrow\right.\) true \(] ?\)
(d) What is \(\operatorname{Pr}\left[\mathcal{A}_{2} \diamond \mathcal{L}_{2} \Rightarrow\right.\) true \(] ?\)
In each problem, a pair of libraries are described. State whether or not \(\mathcal{L}_{\text {left }} \equiv \mathcal{L}_{\text {right }}\). If so, show how they assign identical probabilities to all outcomes. If not, then describe a successful distinguisher.
Assume that both libraries use the same value of \(n\). Does your answer ever depend on the choice of \(n\)?
In part (a), \(\bar{x}\) denotes the bitwise-complement of \(x\). In part \((\mathrm{d}), x \& y\) denotes the bitwise-AND of the two strings:
Show that the following libraries are interchangeable:
Note that \(x\) and \(y\) are swapped in the first two lines, but not in the return statement.
Show that the following libraries are not interchangeable. Describe an explicit distinguishing calling program, and compute its output probabilities when linked to both libraries:
In abstract algebra, a (finite) group is a finite set \(\mathbb{G}\) of items together with an operator \(\otimes\) satisfying the following axioms:
- Closure: for all \(a, b \in \mathbb{G}\), we have \(a \otimes b \in \mathbb{G}\).
- Identity: there is a special identity element \(e \in \mathbb{G}\) that satisfies \(e \otimes a=a \otimes e=a\) for all \(a \in \mathbb{G}\). We typically write " 1 " rather than \(e\) for the identity element.
- Associativity: for all \(a, b, c \in \mathbb{G}\), we have \((a \otimes b) \otimes c=a \otimes(b \otimes c)\).
- Inverses: for all \(a \in \mathbb{G}\), there exists an inverse element \(b \in \mathbb{G}\) such that \(a \otimes b=b \otimes a\) is the identity element of \(\mathbb{G}\). We typically write " \(a^{-1}\) " for the inverse of \(a\).
Define the following encryption scheme in terms of an arbitrary group \((\mathbb{G}, \otimes)\) :
- 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}\) ?
- Fill in the details of the Dec algorithm and prove (using the group axioms) that the scheme satisfies correctness.
- Prove that the scheme satisfies one-time secrecy.
In the proof of Claim \(2.9\) we considered an attacker / calling program that calls \(\operatorname{CTXT}\left(0^{\lambda}\right)\).
- How does this attacker’s effectiveness change if it calls CTXT \(\left(1^{\lambda}\right)\) instead?
- How does its effectiveness change if it calls \(\operatorname{CTxT}(m)\) for a uniformly chosen \(m\) ?
The following scheme encrypts a plaintext by simply reordering its bits, according to the secret permutation \(k\).
Show that the scheme does not have one-time secrecy, by constructing a program that distinguishes the two relevant libraries from the one-time secrecy definition.
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.
Consider the following encryption scheme. It supports plaintexts from \(\mathcal{M}=\{0,1\}^{\lambda}\) and ciphertexts from \(C=\{0,1\}^{2 \lambda}\). Its keyspace is:
\[\mathcal{K}=\left\{k \in\left\{\odot, 1,_{-}\right\}^{2 \lambda} \mid k \text { contains exactly } \lambda \text { "_" characters }\right\}\]
To encrypt plaintext \(m\) under key \(k\), we "fill in" the - characters in \(k\) using the bits of \(m\).
Show that the scheme does not have one-time secrecy, by constructing a program that distinguishes the two relevant libraries from the one-time secrecy definition.
Example: Below is an example encryption of \(m=1101100001 .\) \[\begin{aligned} k &=1_{--} 0_{-} 11010_{-} 1_{-} 0_{-} 0_{--} \\ m &=1101 \quad 100001 \\ \Rightarrow \operatorname{Enc}(k, m) &=11100111010110000001 \end{aligned}\]
Suppose we modify the scheme from the previous problem to first permute the bits of \(m\) (as in Exercise 2.7) and then use them to fill in the "_"characters in a template string. In other words, the key specifies a random permutation on positions \(\{1, \ldots, \lambda\}\) as well as a random template string that is \(2 \lambda\) characters long with \(\lambda\) " " characters.
Show that even with this modification the scheme does not have one-time secrecy.
Prove that if an encryption scheme \(\Sigma\) has \(|\Sigma . \mathcal{K}|<|\Sigma . \mathcal{M}|\) then it cannot satisfy onetime secrecy. Try to structure your proof as an explicit attack on such a scheme (i.e., a distinguisher against the appropriate libraries).
The Enc algorithm of one-time pad is deterministic, but our definitions of encryption allow Enc to be randomized (i.e., it may give different outputs when called twice with the same \(k\) and \(m\). For full credit, you should prove the statement even for the case of Enc is randomized. However, you may assume that Dec is deterministic.
Hint: The definition of interchangeability does not place any restrition on the running time of the distingusher/calling program. Even an exhaustive brute-force attack would be valid.
Let \(\Sigma\) denote an encryption scheme where \(\Sigma . C \subseteq \Sigma . \mathcal{M}\) (so that it is possible to use the scheme to encrypt its own ciphertexts). Define \(\Sigma^{2}\) to be the following nested-encryption scheme:
Prove that if \(\Sigma\) satisfies one-time secrecy, then so does \(\Sigma^{2}\).
Let \(\Sigma\) denote an encryption scheme and define \(\Sigma^{2}\) to be the following encrypt-twice scheme:
Prove that if \(\sum\) satisfies one-time secrecy, then so does \(\Sigma^{2}\).
Prove that an encryption scheme \(\Sigma\) satisfies one-time secrecy if and only if the following two libraries are interchangeable:
Note: you must prove both directions of the if-and-only-if with a hybrid proof.
Prove that an encryption scheme \(\Sigma\) has one-time secrecy if and only if the following two libraries are interchangeable:
Note: you must prove both directions of the if-and-only-if with a hybrid proof.
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.
- Suppose someone tries to prove that one-time secrecy implies two-time secrecy. Show where the proof appears to break down.
- Describe an attack demonstrating that one-time pad does not satisfy your definition of two-time secrecy.
In this problem we consider modifying one-time pad so that the key is not chosen uniformly. Let \(\mathcal{D}_{\lambda}\) denote the probability distribution over \(\{0,1\}^{\lambda}\) where we choose each bit of the result to be \(\theta\) with probability \(0.4\) and 1 with probability \(0.6\).
Let \(\sum\) denote one-time pad encryption scheme but with the key sampled from distribution \(\mathcal{D}_{\lambda}\) rather than the uniform distribution on \(\{0,1\}^{\lambda}\).
- Consider the case of \(\lambda=5\). A calling program \(\mathcal{A}\) for the \(\mathcal{L}_{\text {ots- } \star}^{\Sigma}\) libraries calls EAVESDROP \((01011,10001)\) and receives the result 01101 . What is the probability that this happens, assuming that \(\mathcal{A}\) is linked to \(\mathcal{L}_{\mathrm{ots}-\mathrm{L}}\) ? What about when \(\mathcal{A}\) is linked to \(\mathcal{L}_{\text {ots-R }}\) ?
- Turn this observation into an explicit attack on the one-time secrecy of \(\Sigma\).
Complete the proof of Theorem \(2.16 .\)
- Formally prove (using the hybrid technique) that the scheme in that theorem satisfies one-time secrecy.
- Give a distinguishing calling program to show that the scheme doesn’t satisfy one-time uniform ciphertexts.