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} = (\frac{y _{q} - y _{p}}{x _{q} - x _{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} = (\frac{A _{q}}{B _{q}})^{2} * (\frac{A _{p}}{B _{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})$

tlsn-docs

Key Exchange