# Key Exchange

In TLS, the first step towards obtaining TLS session keys is to compute a shared secret between the client and the server by running the ECDH protocol. The resulting shared secret in TLS terms is called the pre-master secret `PMS`

.

Using the notation from Wikipedia, below is the 3-party ECDH protocol between the `Server`

the `Requester`

and the `Notary`

, enabling the `Requester`

and the `Notary`

to arrive at shares of `PMS`

.

`Server`

sends its public key $Q_{b}$ to`Requester`

, and`Requester`

forwards it to`Notary`

`Requester`

picks a random private key share $d_{c}$ and computes a public key share $Q_{c}=d_{c}∗G$`Notary`

picks a random private key share $d_{n}$ and computes a public key share $Q_{n}=d_{n}∗G$`Notary`

sends $Q_{n}$ to`Requester`

who computes $Q_{a}=Q_{c}+Q_{n}$ and sends $Q_{a}$ to`Server`

`Requester`

computes an EC point $(x_{p},y_{p})=d_{c}∗Q_{b}$`Notary`

computes an EC point $(x_{q},y_{q})=d_{n}∗Q_{b}$- Addition of points $(x_{p},y_{p})$ and $(x_{q},y_{q})$ results in the coordinate $x_{r}$, which is
`PMS`

. (The coordinate $y_{r}$ is not used in TLS)

Using the notation from here, our goal is to compute $x_{r}=(x_{q}−x_{p}y_{q}−y_{p} )_{2}−x_{p}−x_{q}$ in such a way that

- Neither party learns the other party's $x$ value
- Neither party learns $x_{r}$, only their respective shares of $x_{r}$.

We will use two maliciously secure protocols described on p.25 in the paper Eﬃcient Secure Two-Party Exponentiation:

`A2M`

protocol, which converts additive shares into multiplicative shares, i.e. given shares`a`

and`b`

such that`a + b = c`

, it converts them into shares`d`

and`e`

such that`d * e = c`

`M2A`

protocol, which converts multiplicative shares into additive shares

We apply `A2M`

to $y_{q}+(−y_{p})$ to get $A_{q}∗A_{p}$ and also we apply `A2M`

to $x_{q}+(−x_{p})$ to get $B_{q}∗B_{p}$. Then the above can be rewritten as:

$x_{r}=(B_{q}A_{q} )_{2}∗(B_{p}A_{p} )_{2}−x_{p}−x_{q}$

Then the first party locally computes the first factor and gets $C_{q}$, the second party locally computes the second factor and gets $C_{p}$. Then we can again rewrite as:

$x_{r}=C_{q}∗C_{p}−x_{p}−x_{q}$

Now we apply `M2A`

to $C_{q}∗C_{p}$ to get $D_{q}+D_{p}$, which leads us to two final terms each of which is the share of $x_{r}$ of the respective party:

$x_{r}=(D_{q}−x_{q})+(D_{p}−x_{p})$