1 of 17

Lec 13: Jacobi Symbol and DDH Algorithms

2 of 17

Recall Diffie-Hellman key exchange

​

​

​

​

​

​

​

  • If you only need a secret value → CDH suffices
  • If you need a (pseudo)random value → need DDH

 

 

 

 

 

 

 

3 of 17

Decisional Diffie-Hellman (DDH)

  •  

4 of 17

  •  

5 of 17

Recall quadratic residue subgroup

  •  

6 of 17

  •  

7 of 17

  •  

​

​

​

yes

yes

yes

yes

no

yes

no

yes

yes

no

no

no

8 of 17

  •  

​

​

​

yes

yes

yes

yes

no

yes

no

yes

yes

no

no

no

9 of 17

  •  

10 of 17

  •  

11 of 17

Jacobi Symbol

12 of 17

  •  

13 of 17

  •  

14 of 17

  •  

15 of 17

 

  •  

16 of 17

  •  

17 of 17

Student presentations reminder

  • No class next week
  • Presentations begin 11/17 (Mon)
    • Sign up if you haven’t
    • If you know your topic, add it to the sign-up sheet

​

  • 30-40mins
    • High-level expectation: similar to my lectures
    • Detailed expectation → see “Suggested Topics for Student Presentations”