Loading

Module 1: Cyclic Groups

Notes
Study Reminders
Support
Text Version

Cyclic groups - Lesson Summary

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

The key points from this module are:
The Discrete Log assumption in a cyclic group is divided into three namely: 

The discrete Log Logarithm Assumption (DL)
The Computational Diffie-Hellman Assumption (CDH)
The Decisional Diffie-Hellman Assumption

The applications of the Discrete Log assumptions are:

Constructing Fixed-Length Collision-resistant Compression function 
Commitment Schemes in the Standard model (Pederson's Commitment Scheme)

To instantiate Cryptographic primitives based on the Hardness of Dlog, CDH and DDH assumptions, we need to appropriately choose the underlying Cyclic group (G,o); If DLog, CDH, and DDH are computationally easy in the underlying (G,o) then the resultant of the Cryptographic primitive will no longer be secure.
The relationship between the Dlog, CDH and DDH assumptions are:


 


1. If CDH-assumption holds in (G,o), Dlog-assumption also holds in (G,o)

2. If Dlog problem is Computationally easy to solve in (G,o), so is the CDH problem


3. If Dlog assumption holds in (G,o), we do not know if the CDH-assumption holds
4.  if DDH-assumption holds in (G,o), then the CDH-assumption also holds in (G,o)
5. If CDH problem is Computationally easy to solve in (G,o), so is the DDH problem
6. If CDH-assumption holds in (G,o), the DDH-assumption does not hold
 
A Public-Key Encryption Scheme is a triplet of algorithm namely;


The Key Generation algorithm (Gen)
The Encryption algorithm (Enc)
The Decryption algorithm(Dec