Cryptography /Computer Network Security
Computer Network Security
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)
