problem 1Consider the following variants of the RSA public-key encryption scheme: 1) textbook RSA; 2) padded RSA; 3) OAEP+ RSA. Which of the following statements is true, under the RSA intractability assumption and possibly the existence of random oracles?
a. Textbook RSA (on random messages) satisfies one-wayness;
Padded RSA (when the pad is long enough) and OAEP+ RSA satisfy indistinguishability against chosen ciphertext attacks
b. Textbook RSA (on random messages), Padded RSA (when the pad is long enough) and OAEP+ RSA satisfy indistinguishability against chosen plaintext attacks
c. Textbook RSA (on random messages) and Padded RSA (when the pad is long enough) satisfy one-wayness; OAEP+ RSA satisfy indistinguishability against chosen ciphertext attacks
d. Textbook RSA (on random messages), Padded RSA (when the pad is long enough) and OAEP+ RSA satisfy indistinguishability 

problem 2
Which of the following statements about the RSA encryption scheme is known to be true ?
a. if it satisfies one-wayness (for random messages) then factoring is hard
b. if factoring is hard then it satisfies one-wayness (for random messages) 
c. if it satisfies one-wayness (for random messages) then factoring is easy
d. if factoring is easy then it satisfies one-wayness (for random messages) 

problem 3
Which type of homomorphism is satisfied by the (textbook) RSA encryption 
scheme? (Here, N=pq denotes the modulus used in the public key)
a. a ((Z_N,product mod N),(Z*_{phi(N)},sum mod phi(N)))-homomorphism
b. a ((Z*_N,product mod N),(Z*_{phi(N)},sum mod phi(N)))-homomorphism
c. a ((Z_N,product mod N),(Z_N,product mod N))-homomorphism
d. a ((Z*_N,product mod N),(Z*_N,product mod N))-homomorphism

problem 4
Consider the El Gamal encryption scheme, a symmetric encryption scheme (KG,E,D), and the following hybrid encryption scheme having an encryption algorithm that, on input a public key (G,q,g,h), where h=g^x, returns (c1,c2). For which of the following c1,c2 values (and assuming a suitable definition of the key generation and decryption algorithms) does the hybrid encryption scheme satisfy indistinguishability in the presence of chosen message attack?
a.
c1=g^y, c2=E(k,m), where k = g and y is random
b.
c1=g^y, c2=E(k,m), where k = h and y is random
c.
c1=g^y, c2=E(k,m), where k =g^y and y is random
d.
c1=g^y, c2=E(k,m), where k = h^y and y is random

problem 5
Consider the textbook RSA public-key encryption (KG,E,D), where the public key returned by KG is denoted as (e,n), the secret key returned by KG is the pair of primes (p,q), the plaintext input to E is denoted as m and the ciphertext output by E is denoted as c. Which of the following values is closer to c when p=23, q=31, e=49 and m=347?
a. 270
b. 90
c. 630
d. 450

problem 6
Which of the following public-key encryption schemes is known to be insecure against a chosen-plaintext attack?
a. Textbook RSA
b. The scheme computing the ciphertext as the output of a trapdoor permutation that takes as input the plaintext
c. Any deterministic public-key encryption scheme
d. All of the above

problem 7
Assume an encryption scheme is homomorphic. Which of these properties it does not satisfy?
a. perfect secrecy
b. indistinguishability in the presence of a chosen ciphertext attack
c. indistinguishability in the presence of a chosen plaintext attack
d. indistinguishability

problem 8
Which of these schemes would be your first choice as an encryption scheme in applications where, respectively, (1) the maximum security and efficiency are desired, and (2) the maximum efficiency and applicability to computing on encrypted data are desired?
a. (1) Cramer-Shoup's scheme and (2) Paillier's scheme
b. (1) Cramer-Shoup's scheme and (2) Gentry's scheme
c. (1) A hybrid scheme where the asymmetric scheme is Cramer-Shoup's scheme and the symmetric scheme is a secure transmission scheme and (2) Gentry's scheme
d. (1) A hybrid scheme where the asymmetric scheme is Cramer-Shoup's scheme and the symmetric scheme is a secure transmission scheme and (2) Paillier's scheme

problem 9
Which of the following schemes is known to be insecure against a chosen-ciphertext attack?
a. Textbook RSA
b. El Gamal
c. The scheme based on trapdoor permutations and hardcore predicates
d. All of the above

problem 10
Assume an encryption scheme is malleable. Which of these properties it does not satisfy?
a. perfect secrecy
b. indistinguishability in the presence of a chosen ciphertext attack
c. indistinguishability in the presence of a chosen plaintext attack
d. indistinguishability

problem 11
Computing on encrypted data is an interesting computation paradigm allowing parties to compute functions of encrypted plaintexts without decrypting the plaintexts, but just operating on the ciphertexts. To design a cryptographic protocol for digital election where a trusted authority can compute over encrypted electors' votes, which of the following encryption schemes would you use?
a. The Goldwasser-Micali scheme
b. The (textbook) RSA scheme
c. The El Gamal scheme
d. The Paillier's scheme

problem 12
In certain applications (e.g., data transmission inside computers), one parity bit is added to a message so that the resulting total number of bits (including the message bits plus the parity bit) that are equal to 1 is even, unless the transmission of the message experienced an error in precisely 1 bit (in these applications, errors in 2 or more bits are extremely unlikely and thus this possibility is ignored), in which case the total number of bits equal to 1 is odd. The sender of this message would like to encrypt all the message bits in a way that a different party can still check whether there was an error or not, without need for decrypting (which would imply intruding into the computer's data). Which of the following encryption schemes could be used by the sender?
a. Goldwasser-Micali
b. Rabin
c. Gentry
d. Any of the above

problem 13
Multiple patients would like to submit encrypted medical records in a way that allows a doctor to compute statistics like the probability that none of these patients has a particular disease, without need for decrypting any one of the records (showing the specific user's probability of not having that disease). Which of the following encryption schemes could be used by the patients?
a. El Gamal
b. Paillier
c. Rabin
d. None of the above

problem 14
All of the school students are requested to submit encrypted GPA values in a way that allows a statistician to compute statistics like the average GPA in their school, without need for decrypting any one of the students' GPA values. Which of the following encryption schemes would be good enough for this purpose?
a. El Gamal's scheme
b. A malleable scheme that allows the statistician to divide a GPA value by the number of students
c. Paillier's scheme
d. None of the above

problem 15
What are the advantages of hybrid encryption?
a. It combines the lack of shared keys in private-key encryption with the efficiency of public-key encryption
b. It combines the lack of shared keys in public-key encryption with the efficiency of private-key encryption
c. It combines the lack of entity authentication in public-key encryption with the need for shared keys of private-key encryption
d. It combines the lack of entity authentication in private-key encryption with the need for shared keys of public-key encryption

problem 16
For problem 11, for each of the 4 possible answers, provide a justification of why you chose or did not choose that answer. Enter your justifications as text.