1 of 18

Lec 8: Cyclic Groups

2 of 18

Discrete Logarithm (DL)

  • Most commonly used hardness problem in public-key cryptography (other than RSA)
  • DL itself behind
    • Digital signature schemes: Schnorr, DSA, …
  • Variants of DL behind
    • Public-key encryption schemes: ElGamal, …
    • Key exchange protocols: Diffie-Hellman, …

​

  • Defined over cyclic groups

3 of 18

Cyclic Groups

4 of 18

  •  

5 of 18

  •  

6 of 18

  •  

7 of 18

Computation in a cyclic group

  •  

8 of 18

Prime-order cyclic groups

  •  

9 of 18

  •  

10 of 18

  •  

11 of 18

Examples of Cyclic Groups

12 of 18

 

  •  

13 of 18

 

  •  

14 of 18

  •  

15 of 18

  •  

16 of 18

  •  

17 of 18

Gauss’ theorem

  •  

18 of 18

 

  •