Part 1 of 1 - 1 Question 1 of 16
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
2 Question 2 of 16
Consider the problem of computing discrete logarithms in a cyclic group (G,?), with group’s order m; that is, given the group’s generator g, an element y ∈ G, compute an integer x ∈ Zm such that g ? • • • ? g = y, where there are x − 1 occurrences of ?. Then consider the exhaustive search algorithm to search for the discrete logarithm of y in base g for a cyclic group G of order m. Given this algorithm and its running time t(m,n), we want to infer considerations on computing discrete logarithm in G being easy or conjectured to be hard depending on the choices of m as a function of the length n of the group elements. Let m_easy(n) be a value for m such that computing discrete logarithms in G is easy and m_hard(n) be a value for m such that computing discrete logarithms in G may be conjectured to be hard. Which functions would you select as most meaningful for m_easy(n), m_hard(n)?
A. m_easy(n)=O(n); m_hard(n)=omega(n)
B. m_easy(n)=O(poly(n)); m_hard(n)=O(poly(n))
C. m_easy(n)=O(poly(n)); m_hard(n)=omega(poly(n))
D. m_easy(n)=O(n); m_hard(n)=O(n)
3 Question 3 of 16
You plan to use a public-key cryptosystem based on the RSA trapdoor permutation in three different real-life applications, in which the attacker has, respectively, only one of the following resources: (1) a single computer, (2) a collection of computers distributed across the Internet, and (3) a quantum computer. When choosing the length of the modulus n for the RSA trapdoor permutation, you plan to choose a different length for each of the above three attacker resource scenarios. Which of the following length settings is closer to your choice?
A. (a): 1024; (b): 2048; (c): 4096
B. (a): 512; (b): 1024; (c): I would not use RSA
C. (a) 2048; (b): 4096; (c): I would not use RSA
D. (a) 512; (b): 1024; (c): 2048
4 Question 4 of 16
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.
Which of them is sufficient to construct a trapdoor function?
A. Only (1)
B. Only (2)
C. Only (3)
D. (1), (2), or (3)
5 Question 5 of 16
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)? (Hint: Recall that when two random variables X and Y, the probability that X=x conditioned on Y=y is equal to the probability that X=x.)
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
6 Question 6 of 16
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.
Which of them is sufficient to construct a pseudo-random generator, a pseudo-random function and a pseudo-random permutation?
A. Only (1)
B. Only (2)
C.Only (3)
D.(1), (2), or (3)
7 Question 7 of 16
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
8 Question 8 of 16
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
9 Question 9 of 16
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)
10 Question 10 of 16
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
11 Question 11 of 16
Which among these are the differences between the indistinguishability notion with chosen message attack and the indistinguishability notion with adaptive chosen message attack?
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
12 Question 12 of 16
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 1 2n 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
13 Question 13 of 16
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
14 Question 14 of 16
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)?
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
15 Question 15 of 16
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.
Which of them is sufficient to construct a one-way function?
A. Only (1)
B. Only (2)
C. Only (3)
D. (1), (2), or (3)