Public Key Encryption

Question 1

Definition of Public Key encryption scheme

Question 2

CPA indistinguishability experiment

Question 3

Lemma: determinism and CPA-security, PROOF

Question 4

Def of El Gamal Enc Scheme

Question 5

El Gamal security and proof

Question 6

Def of Goldwasser Micali scheme

Question 7

Security of Goldwasser Micali and proof

Question 8

Pailler isomorphism

Question 9

Definition of Pailler encryption

Question 10

security of pailler encryption and proof

Question 11

Plain RSA encryption

Question 12

padded RSA encryption

Question 13

RSA-lsb encryption

Question 14

RSA-lsb security and proof

Question 15

definition of plain rabin encryption scheme

Question 16

definition of rabin-lsb scheme

Question 17

rabin-lsb scheme security and proof

Question 18

definition of homomorphic enc scheme

Question 19

def of fully homomorphic enc scheme

Answer 19

identical distributions

Question 20

def oracle

Question 21

CCA indistinguishability experiment

Question 22

CCA security

Question 23

Th: homomorphic scheme and CCA security with proof

Question 24

definition of malleability

Question 25

definition of cramer shoup scheme

Question 26

security of cramer shoup with proof

Question 27

security of padded RSA encryption

Question 28

plaintext and ciphertext spaces for each pub enc scheme

Question 29

which pub enc schemes are homomorphic?

Question 30

Exercise 1. Let Π = (Gen,Enc,Dec) be a CPA-secure public-key encryption scheme. Prove that the number of random bits used by Encpk cannot be O(log λ).

Question 31

Exercise 2. Assume a public-key encryption scheme for single-bit messages with no decryption error. Show that, given pk and a ciphertext c computed via c ← Encpk(m), it is possible for an unbounded adversary to determine m with probability 1.

Question 32

Exercise 4. Prove that plain Rabin encryption is vulnerable to the following chosen-plaintext attack. If an adversary is able to get the ciphertexts of the plaintexts m and m + δ, where δ ∈ Z∗ is known to the adversary, then the adversary can compute m.

Question 33

Exercise 6. Show that Goldwasser–Micali encryption is homomorphic.

Question 34

Exercise 8. Show that plain RSA encryption of a message m leaks JN (m), the Jacobi symbol of m mod N.