diffie-hellman key exchange II

Work in Progress

Concept

Diffie-Hellman Key Exchange

  • generalized to some group
Publicparameter:g;pAliceRandomlyselecta2ZA=gaS=Ba=(gb)aoutputCSยก1=MBobRandomlyselectb2ZS=Ab=(ga)bB=gb,EmbedminM,C=AbMAB,C

Essential properties of group

  1. DLOG should be hard for the CDH assumption to hold

    • prevent eavesdroppers from recovering from
    • that way they cannot compute
  2. elements should have compact bitstring representations

    • they need to be stored and sent over a channel efficiently
  3. multiplication and inversion should be efficient

    • naively computing the exponent for large values might be computationally infeasible
    • efficient with square-and-multiply
  4. a large-order element should be available

    • to prevent brute force attacks,
  5. messages must be embedded into

    • or a KEM/DEM construction should avoid direct embedding

only multiplicative modular group and elliptic curves work

Discrete Log

  • (Definition 2.3.6)