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 \gets^/$ /{0, ..., |G| − 1/}$, sends $g^a$ to Bob
• Bob: picks $b \gets^/$ /{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!