Public Key Encryption Flashcards
Definition of Public Key encryption scheme
CPA indistinguishability experiment
Lemma: determinism and CPA-security, PROOF
Def of El Gamal Enc Scheme
El Gamal security and proof
Def of Goldwasser Micali scheme
Security of Goldwasser Micali and proof
Pailler isomorphism
Definition of Pailler encryption
security of pailler encryption and proof
Plain RSA encryption
padded RSA encryption
RSA-lsb encryption
RSA-lsb security and proof
definition of plain rabin encryption scheme
definition of rabin-lsb scheme
rabin-lsb scheme security and proof
definition of homomorphic enc scheme
def of fully homomorphic enc scheme
identical distributions
def oracle
CCA indistinguishability experiment
CCA security
Th: homomorphic scheme and CCA security with proof
definition of malleability
definition of cramer shoup scheme
security of cramer shoup with proof
security of padded RSA encryption
plaintext and ciphertext spaces for each pub enc scheme
which pub enc schemes are homomorphic?
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 λ).
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.
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.
Exercise 6.
Show that Goldwasser–Micali encryption is homomorphic.
Exercise 8.
Show that plain RSA encryption of a message m leaks JN (m), the Jacobi symbol of m mod N.
