Asymmetric cryptosystems

We would like to have the following features:

• Agreeing on a short secret over a public channel
• Confidentially sending a message over a public authenticated channel without sharing a secret with the recipient
• Actual data authentication

This features are implemented with asymmetric cryptosystems: cryptography systems where the keys to encrypt and decrypt are different.

Asymmetric cryptosystems rely on hard problems for which bruteforcing the secret parameter is not the best attack.

Diffie-Hellman key agreement (CDH)

The goal of CDH is to make two parties share secret value with only public messages.

The attacker model is:

• Can eavesdrop anything, but not tamper
• The Computational Diffie-Hellman assumption should hold

Assumption: Let $(G, ·)$ ≡ $\lang g \rang$ be a finite cyclic group, and two numbers $a$, $b$ sampled unif. from $\lbrace 0, . . . , |G| − 1 \rbrace (\lambda = len(a) \approx \log_{2}|G|)$ • given $g^a$, $g^b$ finding $g^ab$ costs more than poly($log|G|$) • Best current attack approach: find either $b$ or $a$ (discrete log problem)

Structure:

• Alice: picks $a \from^$ {0, . . . , |G| − 1}$, sends g a to Bob
• Bob: picks b $ ← {0, . . . , |G| − 1}, sends g b to Alice
• Alice: gets g b from Bob and computes (g b)a
• Bob: gets g a from Bob and computes (g a)b
• $(G, ·)$ is commutative $\to (g^b)^a = (g^a)^b$, we’re done!