Question 1
Let n=pq, where p,q are primes of the same length and let phi be Euler's totient function. Consider the following problems: (P1) computing the output p+q from an input n; (P2) computing the output phi(n) from an input n. Which one of the following statements is true?
a. if P1 is easy then P2 is easy
b. if P1 is hard then P2 is hard
c. P1 and P2 are polynomial-time equivalent
d. All of the above
Question 2
Let n=pq, where p,q are primes of the same length and let phi be Euler's totient function. Consider the following problems: (P1) computing the output p from an input n; (P2) computing the output phi(n) from an input n. Which one of the following statements is true?
a. if P1 is easy then P2 is easy
b. if P1 is hard then P2 is hard
c. P1 and P2 are polynomial-time equivalent
d. All of the above
Question 3
Let us denote as "X ci Y" the fact that random variables X and Y are computationally indistinguishable. Assume (A1,A2) is a pair of efficiently samplable (i.e., a variable sample can be efficiently generated) random variables and assume the same about (B1,B2). Which of these conditions is sufficient to have that (A1,A2) ci (B1,B2)?
a. A1 and A2 are independent, B1 and B2 are independent, A1 ci B1, A2 ci B2
b. A1 ci B1, A2 = A1, B2 = B1
c. A2 ci B2, A1 = A2, B1 = B2
d. All of the above
Question 4
Pseudo-random generators, pseudo-random functions and pseudo-random permutations are computationally indistinguishable, respectively, from
a. a function returning a pseudo-random string, a random function, a random permutation
b. a function returning a random string, a random function, a random permutation
c. a function returning a random string, a random function, a random function
d. All of the above
Question 5
Which of these assumptions is sufficient to construct a pseudo-random generator, a pseudo-random function and a pseudo-random permutation?
a. The hardness of factoring integers that are product of two integers of the same length
b. The hardness of computing discrete logarithms modulo random integers of a given length
c. The hardness of inverting the RSA function
d. Any of the above
Question 6
Which among these are the differences between the perfect indistinguishability notion for classical symmetric encryption schemes and the (computational) indistinguishability notion for modern symmetric encryption schemes?
a. In perfect indistinguishability the adversary's algorithm runs in polynomial time and his advantage can be greater than 0 while in computational indistinguishability the adversary's algorithm is not restricted to run in polynomial time and his advantage has to be equal to 0
b. In perfect indistinguishability the adversary's algorithm is not restricted to run in polynomial time and his advantage can be greater than 0 while in computational indistinguishability the adversary's algorithm runs in polynomial time and his advantage has to be equal to 0
c. In perfect indistinguishability the adversary's algorithm is not restricted to run in polynomial time and his advantage has to be equal to 0 while in computational indistinguishability the adversary's algorithm runs in polynomial time and his advantage can be greater than 0
d. In perfect indistinguishability the adversary's algorithm runs in polynomial time and his advantage has to be equal to 0 while in computational indistinguishability the adversary's algorithm is not restricted to run in polynomial time and his advantage can be greater than 0
Question 7
Assume |s1|=|s2|=n and consider the functions defined, for any s1 and s2, as:
(a) G1(s1,s2)=s1 xor s2, (b) G2(s1,s2)=(s1, s2, s1 xor s2).
We have that:
a. G1 and G2 are pseudo-random generators because their outputs are uniformly (and thus, pseudo-randomly) distributed if so are their input
b. G1 and G2 are not pseudo-random generators because either their outputs are not longer than their inputs or there exists a statistical test that distinguishes their outputs from a random string of the same length
c. G1 and G2 are not pseudo-random generators because either there exists an efficient algorithm that can compute their input from their output or their outputs are not longer than their inputs
d. G1 and G2 can be proved to be pseudo-random generators using a proof by reduction
Question 8
Let us denote as "X ci Y" the fact that random variables X and Y are computationally indistinguishable.
For any random variables X,Y,Z, consider the statements:
(a) if X ci Y then Y ci X,
(b) if X ci Y and Y ci X then X = Y,
(c) if X ci Y and Y ci Z then X ci Z,
(d) if X = Y then X ci Y,
(e) if X ci Y then X = Y.
Which of them are true?
a. (a), (c) and (d)
b. (b), (c) and (d)
c. (b), (c) and (e)
d. (a), (d) and (e)
Question 9
To prove that a permutation P is not a pseudo-random permutation, it suffices to show an efficient oracle adversary that can distinguish, with not negligible probability, the case in which its oracle is P from the case in which its oracle is a random permutation RP with the same input and output domains. To obtain an algorithm that makes this distinction, it suffices to find a distinguishing condition (or a set of them) among the adversary's query inputs and query outputs such that: (a) if the oracle is P, then the condition holds with high (e.g., 1) probability; (b) if the oracle is RP, then the condition holds with low (e.g., negligible) probability. Define the extended FT transform as the permutation that maps (L,M,R) to (R,f_k(R) xor M,f_k(M) xor L), where k is a random key, f is a pseudo-random function, and L,M,R are n-bit strings. Which of the following conditions are distinguishing conditions for the 1-round iteration and 2-round iteration of the extended FT transform, respectively? Notation: (L',R') and (L'',R'') denote the 1-round and 2-round outputs, respectively, of the FT transform on input (L,R); when we run the transform on different inputs, we use the notations (L0,R0), (L1,R1), .... for the inputs, (L0',R0'), (L1',R1'), .... for the 1-round outputs and (L0'',R0''), (L1'',R1''), .... for the 2-round outputs.
The notation for the extended FT transform is analogously defined.
a. 1-round extended FT: (L'=R); 2-round extended FT: (L0 xor L1 = L0'' xor L1'') and (R0=R1)
b. 1-round extended FT: (L'=M); 2-round extended FT: M0=M1, L0=L1 and L0''=L1''
c. 1-round extended FT: L=M=R, and R'=M'; 2-round extended FT: L=M=R, and L''=M''
d. None of the above
Question 10
For modern symmetric encryption schemes, which among these are the differences between the indistinguishability notion and the indistinguishability notion with chosen message attack?
a. In the indistinguishability notion, the adversary can additionally and repeatedly query the E(k,.) algorithm as an oracle, and can later use these queries and responses to generate the two challenge plaintexts m(0) and m(1) and its guess for which message was encrypted as c
b. In the "indistinguishability with chosen message attack" notion, the adversary can additionally and repeatedly query the E(k,.) algorithm as an oracle, and can later use these queries and responses to generate the two challenge plaintexts m(0) and m(1) and its guess for which message was encrypted as c
c. In the "indistinguishability with chosen message attack" notion, the adversary can additionally and repeatedly query the E(k,.) algorithm as an oracle, but cannot later use these queries and responses to generate the two challenge plaintexts m(0) and m(1) and its guess for which message was encrypted as c
d. In the indistinguishability notion, the adversary can additionally and repeatedly query the E(k,.) algorithm as an oracle, but cannot later use these queries and responses to generate the two challenge plaintexts m(0) and m(1) and its guess for which message was encrypted as c
Question 11
Which among these are the differences between the indistinguishability notion with chosen message attack and the indistinguishability notion with adaptive chosen message attack?
Answer
a. In the indistinguishability with chosen message attack notion, the adversary can additionally and repeatedly query the E(k,.) algorithm as an oracle even after seeing the ciphertext and can later use these queries and responses to generate its guess for which message was encrypted as c
b. In the indistinguishability with chosen message attack notion, the adversary can additionally and repeatedly query the E(k,.) algorithm as an oracle even after seeing the ciphertext but cannot later use these queries and responses to generate its guess for which message was encrypted as c
c. In the indistinguishability with adaptive chosen message attack notion, the adversary can additionally and repeatedly query the E(k,.) algorithm as an oracle even after seeing the ciphertext and can later use these queries and responses to generate its guess for which message was encrypted as c
d. In the indistinguishability with adaptive chosen message attack notion, the adversary can additionally and repeatedly query the E(k,.) algorithm as an oracle even after seeing the ciphertext but cannot later use these queries and responses to generate its guess for which message was encrypted as c
Question 12
Let (KG,E,D) be the encryption scheme. Which of the following security notions is satisfied by (KG,E,D)?
Answer
a. security in the sense of indistinguishability
b. security in the sense of indistinguishability against chosen message attack
c. security in the sense of indistinguishability against adaptive chosen message attack
d. none of the above: it is not a symmetric encryption scheme
Question 13
Let G:{0,1}n-->{0,1}2n be a pseudo-random generator and consider the following encryption scheme (KG,E,D), where KG generates a random string k; E, on input key k and a message bit b, returns c = G(k) xor 12n if b=1 or c = G(k) if b=0 and D is naturally defined so to satisfy the decryption correctness property.
Which of the following security notions is satisfied by (KG,E,D)?
a. security in the sense of indistinguishability
b. security in the sense of indistinguishability against chosen message attack
c. security in the sense of indistinguishability against adaptive chosen message attack
d. none of the above
Question 14
Let F:{0,1}^n-->{0,1}^{n} be a pseudo-random function and consider the following encryption scheme (KG,E,D), where KG generates a random string k; E, on input key k and a string m, returns c =F(k,0) xor m and D is naturally defined so to satisfy the decryption correctness property.
Which of the following security notions is satisfied by (KG,E,D)?
a. security in the sense of indistinguishability
b. security in the sense of indistinguishability against chosen message attack
c. perfect secrecy
d. none of the above
Question 15
Let P:{0,1}^n-->{0,1}^{n} be a pseudo-random permutation and consider the following encryption scheme (KG,E,D), where KG generates a random string k; E, on input key k and an n-bit string m, returns c =P(k,m) and D is naturally defined so to satisfy the decryption correctness property.
Which of the following security notions is satisfied by (KG,E,D)?
Answer
a. security in the sense of indistinguishability
b. security in the sense of indistinguishability against chosen message attack
c. perfect secrecy
d. none of the above