Cryptography - Computational Secrecy

 1. Computational Secrecy:

• Computational secrecy currently relies on unproven assumptions: 

we do not currently know how to prove unconditionally that non-trivial encryption schemes are computationally secure

• Computational secrecy only ensures secrecy against attackers running in some bounded amount of time

it says nothing about attackers who can run for an unbounded amount of time

• Computational secrecy allows an attacker to learn information about the message with small probability.

it might be possible for an attacker to learn information with negligible probability

2. Let G be a function mapping n-bit inputs to 2n-bit outputs. Which of the following is true of the pseudo one-time pad encryption scheme based on G?

• The scheme is computationally secret if G is a pseudorandom generator.

3. Which of the following attackers can be used to demonstrate that the shift cipher for 3-character messages does not satisfy perfect indistinguishability?

• Output m0 = 'aaa' and m1 = 'abc'. Given challenge ciphertext C, output 1 if the three characters of C are all different.

4. Define the following function G taking n-bit inputs and producing (n+1)-bit outputs:
G(x)=x∥0, where ∥ denotes concatenation. Which of the following attackers shows that this G is not a pseudorandom function?

• On input an (n+1)-bit string y, output 0 if the last bit of y is 0.

the last bit of G(s) is always 0, in contrast to a random string where the last bit is 0 only half the time

5. Say G is a pseudorandom generator taking n-bit inputs and producing 2n-bit outputs.

• G(r) is computationally indistinguishable from a uniform, 2n-bit string if r is a uniform n-bit string.

6. Setting in which a pseudorandom generator could be applied:

• You have a way to generate random bits at the rate of 100 bits/second, but you need 1,000,000 random bits to run a statistical simulation.

7. Consider a pseudo one-time pad encryption scheme Π constructed using some function G. Which of the following did our proof of security for the pseudo one-time pad show?

• If G is a pseudorandom generator, then Π is computationally secret.