Question 1

Which of these statements summarizes an equivalent form of the perfect secrecy notion?

A. The probability of the ciphertext conditioned by one plaintext is the same as the probability of the ciphertext conditioned by another plaintext

B. Knowledge of the plaintext does not affect the probability of the ciphertext

C. The probability that an adversary, after returning two plaintexts, guesses from a ciphertext c which of these two plaintexts was encrypted as c is 1/2

D. All of the above

Question 2

Consider the one time pad encryption scheme to encrypt a 1-bit message m with a 1-bit key k. Replace the XOR operation with another operation X. For which X(m,k) does the resulting scheme satisfy perfect secrecy? (Recall: a OR b = 1 if and only if at least one of a,b=1; a AND b = 1 if and only if both a,b=1; NOT(a)=1 if and only if a=0.)

A. X(m,k) = (m AND NOT(k)) OR (m AND k)

B. X(m,k) = (NOT(m) AND NOT(k)) OR (m AND k)

C. X(m,k) = (NOT(m) AND k) OR (m AND k)

D. none of the above

Question 3

Which of these are valid properties of the one time pad?

A. satisfies perfect secrecy
B. the length of the key is equal to the length of the message
C. encryption and decryption are very efficient
D. all of the above

Question 4

Consider the one-time pad encryption scheme to encrypt a 1-bit message m. For b=0,1, let E[b] be the event "message m is = b", assume prob(E[0])=p and prob(E[1])=1-p, for some p in [0,1], and let F be the event "ciphertext C is = 0". Which of the following is the probability of event E[0] given that event F happens, when p=0.65?

A. A number >= 0 and < 0.25
B. A number >= 0.25 and < 0.5
C. A number >= 0.5 and < 0.75
D. A number >= 0.75 and < 1

Question 5

You know that a meaningful plaintext in a language with an x-letter alphabet is encrypted using either the mono-alphabetic substitution cipher or the poly-alphabetic substitution cipher (with a key of t random numbers in [1,x], for a known value of t; here, assume t=15 and x=20), but you do not know which of the two ciphers was used. You want to find the plaintext (with probability 1) and are planning to first use an exhaustive (or brute-force) search attack assuming that the mono-alphabetic substitution cipher was used, and then use another exhaustive (or brute-force) search attack assuming that the poly-alphabetic substitution cipher was used. Unfortunately you realize that you have no time for both attacks, and thus decide to run the attack that requires the smallest number of decryption attempts. Choose the best pair of answers to the following questions: (a) Which cipher do you assume in the attack you run? (b) Which number is closer to the number of decryption attempts made by your attack?

A. (a) mono-alphabetic substitution cipher; (b) 2^{60}
B. (a) mono-alphabetic substitution cipher; (b) 2^{80}
C. (a) poly-alphabetic substitution cipher; (b) 2^{60}
D. (a) poly-alphabetic substitution cipher; (b) 2^{80}

Rationale:

Question 6

For which X,Y in {o, O, Theta, Omega, omega}, do the relationships t(n)+t'(n) = X(min(t(n),t'(n))) and t(n)+t'(n) = Y(max(t(n),t'(n))) hold for all t,t' such that t(n),t'(n)>0 ?

A. X=Theta, Y=Theta
B. X=Theta, Y=Omega
C. X=Omega, Y=Theta
D. X=omega, Y=Theta

Question 7

In an encryption scheme, let Enc denote the encryption algorithm, Dec denote the decryption algorithm, and A denote the adversary's algorithm. Furthermore, let e(n), d(n), denote the running times of algorithms Enc, Dec, respectively, and let a(n) denote the minimum running time that an attacker takes to break any such scheme, where n is the security parameter. When designing this scheme following the principles of modern cryptography, which of these relationships would you use to choose your algorithms?

A. e(n),d(n)=O(n^c) and a(n)=Omega(2^{cn}) for some constant c
B. e(n)=O(n^c) and d(n),a(n)=Omega(2^{cn}) for some constant c
C. e(n),d(n),a(n)=O(n^c) for some constant c
D. e(n),d(n),a(n)=Omega(2^{cn}) for some constant c

Question 8

Informally, BPP is the class of languages that can be decided by a probabilistic algorithm in polynomial time with an error probability of at most 1/3 on any instance. More formally, a language L is in BPP if there exists a probabilistic algorithm A (i.e., an algorithm that is allowed to use a polynomial-length string of random bits) that runs in polynomial time and satisfies the following: if x is in L then A(x) returns 1 with probability at least 2/3; if x is not in L then A(x) returns 1 with probability at most 1/3. By performing independent repetitions of algorithm A and taking the majority output, one can amplify the (2/3; 1/3) gap to (1 - 2^{-k}; 2^{-k}), which is extremely close to (1,0). BPP seems to well capture the class of problems that can be efficiently computed by a computer today. It is known that P is in BPP, and while it is conjectured that P = BPP, this is actually unknown. It is also unknown whether BPP is in NP. Consider the following statements:

1) if L1 is polynomial-time reducible to L2, and L2 is in P, then L1 is in BPP;
2) if L1 is polynomial-time reducible to L2, and L2 is in BPP, then L1 is in NP.

They are, respectively:

A. true, unknown
B. unknown, unknown
C. unknown, false
D. true, false

Rationale:

Question 9

For a still merely intuitive notion of "secure" (e.g., it is hard to guess info about the plaintext from the ciphertext), which cryptographic primitives are sufficient to construct a "secure" public-key cryptosystem?

A. a one-way function f and a hard-core predicate P for f

B. a one-way trapdoor function f and a hard-core predicate P for f

C. a one-way trapdoor permutation f

D. a hard-core predicate P for f

Question 10

Assume you want to construct a public-key cryptosystem using the principles of modern cryptography, and you are allowed to choose languages L1, L2 such that your cryptosystem can be proved secure assuming that deciding L1 is easy and L2 is hard; from which of the following complexity classes would you pick L1 and L2?

A. L1 from BPP and L2 from P
B. L1 from P and L2 from BPP
C. L1 from (NP minus BPP) and L2 from BPP
D. L1 from BPP and L2 from (NP minus BPP)

Rationale:

Question 11

You have to choose the length of the modulus n for the RSA trapdoor permutation in use within

your public-key cryptosystem. The attacker has one of the following resources: (a) a single computer, (b) acollection of computers distributed across the Internet, or (c) a quantum computer.

Which of the following lengths for n would you choose?

A. (a): 4096; (b): 512; (c): I would not use RSA
B. (a): 512; (b): 4096; (c): I would not use RSA
C. (a): 2048; (b): 4096; (c): 8196
D. (a): 2048; (b): 4096; (c): I would not use RSA

Question 12

Consider algorithms B.10, B.11, B.12, and B.13 in the [KL] textbook. Which one(s) among these does not run in polynomial time in its input length?

A.
B.10 and B.11
B.
B.10 and B.12
C.
B.11 and B.13
D.
B.12

Question

Factoring is the problem of computing, on input a positive integer n, a factorization of n in terms of integer powers of prime numbers. This problem can be "easy" (i.e., there exists a polynomial-time algorithm that solves it) or "(conjectured to be) hard" (i.e., there seems to be no polynomial-time algorithm that solves it) depending on the (sub)set of integers from which n is chosen. De?ne the trial division algorithm D to solve the factoring problem and study its running time t_D(n). Given this algorithm and its running time, we want to infer considerations on factoring n being easy or conjectured to be hard when n is chosen among products of two primes (i.e., n = pq for some primes p, q). Let m_easy(n) be a value for min(p, q) such that factoring n is easy and m_hard(n) be a value for min(p, q) such that factoring n may be conjectured to be hard. Which functions would you select as most meaningful for t_D(n), m_easy(n), m_hard(n)?

A. t_D(n)=O(n 2); m_easy(n)=O(log n); m_hard(n)=O(square root of n);
B. t_D(n)=O(square root of n); m_easy(n)=O(square root of n); m_hard(n)=O(n);
C. t_D(n)=O(square root of n); m_easy(n)=O(poly(log n)); m_hard(n)=O(n);
D. t_D(n)=O(square root of n); m_easy(n)=O(poly(log n)); m_hard(n)=O(square root of n);

Question 14

Consider the following three assumptions:
1) The hardness of factoring integers that are product of two primes of the same length
2) The hardness of computing discrete logarithms modulo primes
3) The hardness of inverting the RSA function.
Determine which of them is known to be sufficient or not to construct a one-way function. Which of the following statements is true?

A. (1) is sufficient, (2) is sufficient, (3) is sufficient

B. (2) is sufficient, (1) is sufficient, (3) is not known to be sufficient

C. (3) is sufficient, (1) is not known to be sufficient, (2) is not known to be sufficient

D.  (1) is not known to be sufficient, (2) is not known to be sufficient, (3) is not known to be sufficient

Question 15

Consider the following three assumptions:

1) The hardness of factoring integers that are product of two primes of the same length

2) The hardness of computing discrete logarithms modulo primes

3) The hardness of inverting the RSA function.

Determine which of them is known to be sufficient or not to construct a trapdoor permutation. Which of the following statements is true?

A.
(1) is sufficient, (2) is sufficient, (3) is sufficient
B.
(2) is sufficient, (3) is not known to be sufficient
C.
(2) is not known to be sufficient, (3) is sufficient
D.
(1) is not known to be sufficient, (2) is not known to be sufficient, (3) is not known to be sufficient

Rationale:

Question 16

Please enter here your rationale for questions 5,10,15 (only if not entered before).

Maximum number of characters (including HTML tags added by text editor): 32,000