Diffie-Hellman

Introduced by DH86, was a groundbreaking paper that helped secret key cryptography flourish and finally be able to use for public use. Exchanging secret keys over an insecure channel unlocked a whole new realm of protocols which led to creation of RSA, EL-Gamal, signatures, etc.

Computational DH assumption: computational hardness assumption on DH problem. depends on discrete logarithm assumption and states that: In a cyclic group $G$ of order $q$ with a generator $g$, if an adversary knows: $g,g^a,g^b$, then it’s computationally impossible to know $g^{ab}$.

Decisional DH assumption: computational hardness assumption on DH problem. depends on discrete logarithm assumption, states: In a cyclic group $G$ of order $q$ with generator $g$, it’s impossible to distinguish between $g,g^a,g^b,z$ and $g,g^a,g^b,g^{ab}$.

$\mathrm{Pr}[\mathcal{A}(\mathbb{G},q,g,g^x,g^y,g^z)=1]-\mathrm{Pr}[\mathcal{A}(\mathbb{G},q,g,g^x,g^y,g^{xy})=1]\le \text{negl}(n)$

It’s easier to solve DDH in certain groups but harder to solve DLP and thus, it’s a stricter assumption that CDH.

Key-Exchange experiment ${\text{KE}}_{\mathcal{A},\Pi }^{\text{eav}}$:

• Two parties involved, with security parameter $1^n$. Messages exchanged are output as transcript, $\text{Trans}$, and a key $k$ is exchanged between the two.
• $b\in \{0,1\}$ is chosen. If $b=0⟹\hat{k}=k$, else $b=1⟹\hat{k}\leftarrow \{0,1{\}}^n$
• $\mathcal{A}$ is given transcript and $\hat{k}$, outputs a bit $b^{\prime }$
• experiment succeeds if $b^{\prime }=b$, i.e. $\mathcal{A}$ succeeds in distinguishing real key.

$\mathrm{Pr}[{\text{KE}}_{\mathcal{A},\Pi }^{\text{eav}}=1]\le \frac{1}{2}+\text{negl}(n)$

security of DDH defines distinguishability on group elements rather than uniform n-bit strings, but Key-exchange experiment chooses $\hat{k}$ from $\{0,1{\}}^n$. Usually cryptographic keys are created from strings, and not group elements.

Prove $\mathrm{Pr}[{\text{KE}}_{\mathcal{A},\Pi }^{\text{eav}}=1]\le \text{negl}(n)$, if DDH assumption is hard.

DFKE: allows two parties to share a secret over an unsecured channel. it’s hardness is based upon DLP.

sequenceDiagram
participant A as Alice
participant C as Carol
participant B as Bob
Note over A: create private/public key pair
Note over B: create private/public key pair
A->>B: send key $$k_{1}=K^{a}$$
Note over B: compute $$k_{ab}=k_{1}^{b}$$
B->>A: send key $$k_{2}=K^b$$
Note over A: compute $$k_{ab}=k_{2}^{a}$$
Note over C: knows $$k_{1},k_{2}$$ but can't compute $$k_{ab}$$ due to hardness of DLP

does this extend to 3 or maybe n parties? if yes, how?

yes, it can be easily extended to multiple parties but communication complexity is $\mathcal{O}(n^2)$. can improve complexity to $\log (n)+1$ using divide and conquer approach.

There’s certain groups which are believed to be secure against attacks like Babystep-Giantstep or Pohlig-Hellman, described in RFC3526.

Anonymous DH uses ephemeral keys when communicating with any new party, i.e. a new key is generated for each party. When both parties use ephemeral keys it’s called ephemeral-ephemeral DH. When one of the party uses same keys for all communication, it’s called static DH.

• static-static DH
• ephemeral-static DH
• static-static DH

ECDH (Elliptic curve Diffie-Hellman)

Diffie-Hellman key exchange based on elliptic-curves, where the private key is generated randomly and public key is derived from generator of the multiplicative group of the curve. It’s believed to have stronger security guarantees than FFDH (Finite Field Diffie-Hellman) as DLP is a harder problem in elliptic curves.

Tripartite DH: key exchange between three parties using pairing based curves.

sequenceDiagram
participant A as Alice
participant B as Bob
participant C as Carol
Note over A: create private/public key pair: $$a,g^{a}$$
Note over B: create private/public key pair: $$b,g^{b}$$
Note over C: create private/public key pair: $$c,g^{c}$$
B->>A: send public key: $B$
C->>A: send public key $C$
Note over B: find $$K=e(B,C)^{a}$$
A->>B: send public key: $A$
C->>B: send public key $C$
Note over B: find $$K=e(B,C)^{b}$$
A->>C: send public key: $A$
B->>C: send public key $B$
Note over B: find $$K=e(A,B)^{c}$$

shared key: $K=e(A,B{)}^c=e(g^a,g^b{)}^c=e(g,g{)}^{abc}$ using bilinearity property of pairings. Thus, all three parties have same shared key and any adversary only has $A,B,C$ but can’t derive $K$ using DLP assumption.

$e(g,g)=1$ for any pairing and thus, distortion-map $\varphi$ is used to map $e(g,\varphi (g))$ to another r-torsion subgroup.

Twin DH

Tldr

Let there be two parties Alex and Alice,

• Alex has $pk$: $x$, Alice has $pk$: $y$
• Generate public keys: $P_{alex}=xG$, $P_{alice}=yG$
• Send each other public keys
• Calculate new public key $P_s=P_{alex}\ast y$ OR $P_{alice}\ast x$

Attacks on DH

Man in the middle attack: anonymous (unauthenticated) DH is prone to man-in-the-middle attack where an adversary listens to communication between both parties and can change the contents of the message.

sequenceDiagram
participant A as Alice
participant B as Bob
participant C as Carol

Note over A: create private/public key pair: $$a,g^{a}$$
Note over C: create private/public key pair: $$c,g^{c}$$

A-xC:send public key $$A$$, intercepted by B
B->>C:send invalid public key $$A'$$
B->>A:send invalid public key $$B'$$
B->A:Alice thinks communicate with Carol, but actually communicating with Bob
B->C:Carol thinks communicate with Alice, but actually with Bob

References

• DFKE lecture notes
• threshold signature on DH