Skip to main content
Engineering LibreTexts

Exercises

  • Page ID
    7324
  • 2.1: Consider the following encryption scheme:

    Screen Shot 2019-02-16 at 1.05.56 PM.png

    (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\)):

    Screen Shot 2019-02-16 at 12.53.09 PM.png

    (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.

    Screen Shot 2019-02-16 at 12.54.40 PM.png

    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:

    Screen Shot 2019-02-16 at 12.56.35 PM.png

    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:

    Screen Shot 2019-02-16 at 12.57.54 PM.png

    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:

    Screen Shot 2019-02-16 at 12.58.42 PM.png

    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:

    Screen Shot 2019-02-16 at 1.04.36 PM.png