1 of 24

Lec 1: Review of Basic Cryptography

2 of 24

Instructor: Jiayu Xu

  • Third-year assistant professor in EECS, main research interest: cryptography
  • xujiay@oregonstate.edu
  • Office: KEC 2021 (the office shown on my OSU profile page is incorrect)
  • Office hours: 3:00-4:00pm every Thu; or by appointment

3 of 24

What is this class about??

  • Password-Authenticated Key Exchange (PAKE)
    • Active research area since 1992
    • Interesting topic in both theory and practice (used by billions of people on the Internet)
    • This is a class about theory (I don’t care about practical applications)
  • Advanced topic
    • Covers a lot of recent research progress
    • Fast-paced
    • MATERIALS UNFRIENDLY TO BEGINNERS

4 of 24

Prerequisites

  • I ASSUME THAT YOU HAVE TAKEN AN “INTRODUCTION TO CRYPTOGRAPHY” CLASS (or have self-learned the materials in such a class)

5 of 24

Test if you fit this class…

  • Do you know…
    • What a negligible function is?
    • What it means to say an encryption scheme is CPA-secure/CCA-secure?
    • What the DDH/CDH assumption is?
    • What the Random Oracle Model is?

​

  • If not, drop this class

6 of 24

Logistics

  • 17-19 lectures, attendance expected
    • If you cannot/don’t want to attend, talk to me in advance

7 of 24

  • 3 homework assignments (60%) + 1 research proposal (40%)
  • Homework: 1-2 problems
    • Read and summarize papers
    • Very minor research problems
    • You can discuss orally but must write up solutions yourself
  • Research proposal: 1-3 pages
    • Topic
    • Existing works
    • Open problem(s) you want to solve
    • Plan to solve the problem(s)
    • You don’t need to carry out the research plan yourself; however, you should convince me that the plan can be carried out by others

8 of 24

Key Exchange Protocols

9 of 24

 

 

10 of 24

Basic security of key exchange protocols

  •  

11 of 24

  •  

12 of 24

Alternative (but equivalent) definition

  •  

13 of 24

Diffie-Hellman Key Exchange

14 of 24

​

​

​

​

​

​

  • Secure against an eavesdropper assuming the Decisional Diffie-Hellman (DDH) assumption

 

 

 

 

 

 

 

15 of 24

If you want to use Computational Diffie-Hellman (CDH)…

  •  

 

 

 

 

 

 

 

16 of 24

Security of hashed Diffie-Hellman key exchange

  •  

17 of 24

  •  

18 of 24

First claim

  •  

19 of 24

  •  

20 of 24

  •  

21 of 24

Second claim

  •  

22 of 24

  •  

23 of 24

Diffie-Hellman key exchange is insecure against a man-in-the-middle adversary

  •  

 

 

 

 

 

 

24 of 24

  • No way to prevent impersonation attacks without any trusted setup
  • Authenticated Key Exchange (AKE): KE protocol with certain setup, secure against man-in-the-middle adversaries