Simplified 2PC point addition

[themighty1]

The current point_addition protocol can be greatly simplified.

We will use the M2A and A2M protocols from https://www.cs.umd.edu/~fenghao/paper/modexp.pdf (p. 25)

From the original write-up (https://tlsnotary.org/how_it_works#section1) we want to compute in 2PC the additive shares of $(\frac{y_q-y_p}{x_q-x_p})^2 - x_p - x_q$

For clarity, expanding the above into 3 terms A*B+C :

$(y_q^2 - 2y_qy_p + y_p^2) * (\frac{1}{x_q^2 - 2x_qx_p + x_p^2}) + (- x_p - x_q)$

Term A:

• compute additive shares of $2y_qy_p$ using M2A, then each party respectively adds $y_q^2$ and $y_p^2$ to their additive share. The result is additive shares $A_p$ and $A_q$

Term B:

• compute additive shares of $2x_qx_p$ using M2A, then each party respectively adds $x_q^2$ and $x_p^2$ to their additive share. The result is $\frac{1}{D_p + D_q}$.

• compute multiplicative shares of $D_p + D_q$ using A2M, the result is $(\frac{1}{M_p}) * (\frac{1}{M_q})$.

• each party locally computes an inverse of their share M and calls it MInv

• compute additive shares of $MInv_p * MInv_q$ using M2A. The result is additive shares $B_p$ and $B_q$

Term A * B:

Given that $(A_p + A_q)*(B_p + B_q) = A_pB_p + A_pB_q + A_qB_p + A_qB_q$, the 1st and the 4th terms each party computes locally but the 2nd and the 3rd terms are computed using M2A. The result is additive shares $AB_p$ and $AB_q$

Term C:

Finally, the respective party locally subtracts $AB_p - x_p$ and $AB_q - x_q$ and arrives at their point addition shares.

[th4s]

Ack, makes sense for me.

[themighty1]

Update: this OT-only approach is not worth pursuing since wasm BigInt operations will likely have native speed in the browser and are not the bottleneck.

The M2A and A2M protocols can be implemented using only OT, not requiring any Paillier operations. This will be especially useful on wasm targets where Paillier operation will slow us down.

M2A can be implemented using the Gilboa OT protocol. A2M can be implemented using the protocol described in https://eprint.iacr.org/2008/465 (bottom of p.5 the paragraph Unconditionally secure product-sharing)

To make the protocol maliciously secure we can use a DualEx approach where parties run point addition twice, switching roles and then at the end run the equality check similar as in step 3 ( A) or B) ) in https://github.com/tlsnotary/tlsn/issues/70#issuecomment-1285944053

The extra bandwidth cost compared to the Paillier approach is ~200KB

[themighty1]

We can decrease the number of communication rounds from 3 to 2 in this way.

From the original write-up (https://tlsnotary.org/how_it_works#section1) we want to compute in 2PC: $(\frac{y_q-y_p}{x_q-x_p})^2 - x_p - x_q$

Round 1:

Using A2M, the parties first convert $y_q-y_p$ and then convert $x_q-x_p$ into multiplicative shares $A * B$ and $C * D$, respectively, which leads us to

$(\frac{A}{C})^2 * (\frac{B}{D})^2 - x_p - x_q$

The parties then locally square their respective terms and convert the fractions (mod p) into integers (mod p) which leads to

$E * F - x_p - x_q$

Round 2:

The parties use M2A to convert $E * F$ into additive shares.

[valpaq]

Hi, is it still active issue? if no one already working on it, I wanna help, however will ask clarification questions, okay?

[sinui0]

Hi @valpaq thanks for showing interest. I believe this issue will be closed by #190

[themighty1]

thank you. closing since that PR implemented it.