1 of 16

Lecture 16: Public-Key Encryption Schemes (I)

2 of 16

  • Key exchange: distribute key for encryption scheme
  • Can we get rid of key distribution problem altogether?

​

​

​

  • “Anyone can encrypt; only the secret key holder can decrypt”

​

private-key encryption

public-key encryption

Sender/encryptor

​

​

Receiver/decryptor

​

​

3 of 16

  • “Anyone can encrypt; only the secret key holder can decrypt”
  • Key distribution can be done via public channel

 

 

 

 

4 of 16

  •  

5 of 16

EAV-security for public-key encryption schemes

  •  
  •  

 

6 of 16

  •  

7 of 16

ElGamal Encryption Scheme

8 of 16

Recall Decisional Diffie-Hellman (DDH) assumption

  •  

9 of 16

ElGamal encryption scheme

  •  

10 of 16

  •  

11 of 16

Security proof

  •  

 

 

12 of 16

 

  •  
  •  

 

13 of 16

Step 2: replace ciphertext with random garbage

  •  
  •  

 

14 of 16

  •  

15 of 16

  •  

16 of 16

Putting it together

  •