1 of 17

Lec 12: Self-Correction for DL and CDH

2 of 17

DL Self-Correction

3 of 17

  •  

4 of 17

  •  

5 of 17

  •  

6 of 17

Random self-reducibility

  • A hard problem is random self-reducible if
  • “A good algorithm in average case implies a good algorithm in worst case”

7 of 17

CDH Self-Correction

8 of 17

Computational Diffie-Hellman (CDH)

  •  

9 of 17

Diffie-Hellman key exchange

  • Scenario: 2 people want to agree upon a secret value. There is an adversary (“eavesdropper”) that can see everything sent between you two. You want to make sure that even then the adversary cannot compute the secret value

10 of 17

​

​

​

​

​

  • If you only need a secret value → CDH suffices
  • If you need a (pseudo)random value → need Decisional Diffie-Hellman (DDH, later)

 

 

 

 

 

 

 

11 of 17

CDH self-correction

  •  

12 of 17

  •  

13 of 17

Step 1: multi-output CDH solver with overwhelming winning probability

  •  

14 of 17

Step 2: extract correct answer from multi-output CDH solver

  •  

15 of 17

  •  

16 of 17

  •  

17 of 17

References

  • [Shoup97] Victor Shoup. Lower Bounds for Discrete Logarithms and Related Problems. In EUROCRYPT 1997.
  • [CKS08] David Cash, Eike Kiltz, and Victor Shoup. The Twin Diffie-Hellman Problem and Applications. In EUROCRYPT 2008.