1 of 17

Lecture 15: Key Exchange Protocols

2 of 17

Recap

  •  

3 of 17

Discrete Logarithm

4 of 17

Setup

  •  

5 of 17

Discrete logarithm (DL) assumption

  •  

6 of 17

Algorithms for DL

  •  

7 of 17

Diffie-Hellman Key Exchange

8 of 17

How to people agree upon a key?

  • 2 people with a secure channel in advance

​

​

  • Later…

​

​

​

​

​

  • What if you don’t have a secure channel in advance??

 

 

 

 

 

 

9 of 17

Key exchange protocol

  •  

 

 

 

 

 

10 of 17

  •  

 

 

 

 

 

11 of 17

Diffie-Hellman key exchange

  •  

 

 

 

 

 

 

 

12 of 17

  •  

 

 

 

 

 

 

 

13 of 17

Decisional Diffie-Hellman (DDH) assumption

  •  
  •  

 

14 of 17

DL v. DDH

  •  

15 of 17

  •  

16 of 17

  • Diffie-Hellman key exchange insecure against man-in-the-middle adversaries (that can modify messages)

 

 

 

 

 

 

17 of 17

  • General lesson: cannot protect against man-in-the-middle adversaries if absolutely no trusted setup
    • Adversary can do whatever an honest party does
    • …and get whatever an honest party gets
  • Authenticated key exchange (AKE): secure against man-in-the-middle adversaries with some “mild” setup