Improved Secure Two-party Computation from a Geometric Perspective
In secure 2PC, a linear share of a secret \(x\) is \(x = x_{0} + x_{1} \mod L\) for some \(L = 2^{l}\). For \(x\in \mathbb{Z}_{L}\), \(uint(x) = x\mod L\) is the unsigned representation. We can also represent a signed number in \(\mathbb{Z}_{}_{L}\) by treating the first \(L/2\) numbers as positives, and the next half as negatives. E.g., For \(L=8\), the elements of \(\mathbb{Z}_{L}\) are \(\{0,1,2,3,4,5,6,7\}\) which are all unsigned integers. For the signed integers, we can represent these as \(\{0,1,2,3,-4,-3,-2,1\}\) by setting \(int(x) = uint(x) - MSB(x)\cdot L\). When using linear shares \(x_{0}\) and \(x_{1}\), we have
- \(uint(x) = x_{0} + x_{1}\) when \(x_{0} + x_{1} < L\)
- \(uint(x) = x_{0} + x_{1} - L\) when \(x_{0} + x_{1} > L\)
We write this as \(uint(x) = x_{0} + x_{1} - Wrap(x_{0}, x_{1}, L)\cdot L\) Now \(int(x) = uint(x) - MSB(x) \cdot L\), which is \(int(x) = x_{0} + x_{1} - Wrap(x_{0}, x_{1}, L)\cdot L - MSB(x)\cdot L\), which is \(int(x) = x_{0} + x_{1} - (Wrap(x_{0}, x_{1}, L) + MSB)\cdot L\) The coefficient of \(L\) is defined as \(MW(x) = Wrap(x_{0}, x_{1},L ) + MSB(x)\)
Computing \(MW(x)\) is expensive. This paper presents a more efficient way. The observation is that if \(|x| < L/3\), then
- \(MW(x) = 0\) iff \(x_{0} \in [0,L/3)\) and \(x_{1} \in [0,L/3)\)
- \(MW(x) = 2\) iff \(x_{0} \in [2L/3, L)\) and \(x_{1} \in [2L/3, L)\)
- \(MW(x) = 1\) everywhere else
Now, two parties can locally check condition 1 and 2 on their shares, and use two AND gates to check if they are in CONDITION 1 or 2. If neither, they know that \(MW(x) = 1\).
This reduces the cost of a comparison from computing WRAP and MSB to two AND gates.
They use this technique to speed up 3 problems:
- Truncation: \(x \gg k = \lfloor int(x) / 2^{k} \rfloor\). We can efficiently compute this using
\(x \gg k = \lfloor x_{0} / 2^{k} \rfloor + \lfloor x_{1} / 2^{k} \rfloor - MW(x) \cdot 2^{(l-k)}+\delta\) (after substituting the formula for \(int(x)\) and the formula that \(\lfloor (a+b) /d \rfloor = \lfloor a/d \rfloor + \lfloor b/d \rfloor + \delta\) where \(\delta = 1\{(a \mod d) + (b\mod d) \ge d\}\)). So here \(\delta = Wrap(x_{0} \mod 2^{k}, x_{1} \mod 2^{k} , 2^{k}\).
- We can do the \(MW(x)\) part faster because of the geometric observation.
- There is something called a one-bit error version where the \(\delta\) term is ignored, there this technique yields much more improvements.
Signed extension protocols. Convert an $m$-bit signed number into a $n$-bit signed number (\(n>m\)).
- If \(x\in Z_{M}\) is an integer with shares \(x_{0}\) and \(x_{1}\), we want \(y\in Z_{N}\) and shares \(y_{0}\) and \(y_{1}\) such that \(int(x) = int(y)\).
- Substituting formulas, we get \(x_{0} + x_{1} - MW(x)\cdot M = y_{0} + y_{1} - MW(y)\cdot N\).
- The paper shows that \(MW(x) = MW(y)\).
- Then, we get \(y_{0} + y_{1} = x_{0} + x_{1} + MW(x) \cdot (N-M)\).
- Then they obtain a secret share of \([MW(x)]\) and set \(y_{0} = x_{0} + [MW(x)]\cdot (N-M)\) and \(y_{1} = x_{1} + [MW(x)]\cdot (N-M)\).
- Now, computing \(int(y)\) is \(int(x)\), thus a successful signed extension.
The lemma that states \(MW(x) = MW(y)\) works as per the following cases:
- Case 1: \(x_{0} + x_{1} \in [0, M/2)\). This is the case where \(x\) is a positive integer and the shares do not wrap.
- For \(x\), \(Wrap(x) = 0\), \(MSB(x) = 0\). Therefore, \(MW(x) = 0\)
- For \(y\), \(y_{0} = x_{0}\), \(y_{1} = x_{1}\). Therefore, \(y_{0} + y_{1} = x_{0} + x_{1} < M/2 < N/2\).
- So, \(Wrap(y) = 0\), \(MSB(y) = 0\). Therefore, \(MW(y) = 0\).
- Therefore, \(MW(x) = MW(y)\).
- Case 2: \(x_{0} + x_{1} \in [M/2, M)\). This is a negative integer.
- So, \(int(x) = x_{0} + x_{1} - M\)
- For \(x\), \(Wrap(x) = 0\), \(MSB(x) = 1\). Therefore, \(MW(x) = 1\)
- \(int(x) = x_{0} + x_{1} -M = int(y)\)
- For \(y\), Set \(y_{0} = x_{0}\). Since \(x\) is negative, we have \(MSB(y) = 1\) to keep it negative. This results in \(int(y) = y_{0} + y_{1} - N\). This gives us \(x_{1} - M = y_{1} - N\) or \(y_{1} = x_{1} + N - M\).
- Now, \(y_{0} + y_{1} \in [N-M/2, N)\). This results in \(Wrap(y) = 0\).
- Hence, \(MW(x) = MW(y) = 1\).
- Case 3: \(x_{0} + x_{1} \in [M, 3M/2)\). This represents a positive integer where shares wrap around.
- For \(x\), \(Wrap(x) = 1\) (since \(x_{0} + x_{1} \geq M\)), \(MSB(x) = 0\) (since the actual value \(x = x_{0} + x_{1} - M < M/2\)). Therefore, \(MW(x) = 1\).
- \(int(x) = x_{0} + x_{1} - M = int(y)\)
- For \(y\), set \(y_0 = x_0\). Since \(x\) is positive, we want \(MSB(y) = 0\). So, we want \(y_{0} + y_{1} \in [0,N/2) \cup [N, 3N/2)\).
- For the first case, we have \(int(y) = y_{0} + y_{1}\), which gives us \(y_{1} = x_{1} - M\). But this makes \(y_{1}\) negative which is not allowed.
- For the second case, we have \(int(y) = y_{0} + y_{1} - N\) which gives us \(y_{1} = x_{1} + N - M\) which works.
- Now, we have \(y_{0} + y_{1} \in [N, 3N/2)\), so \(Wrap(y) = 1\).
- Hence, \(MW(y) = MW(x) = 1\).
- Case 4: \(x_{0} + x_{1} \in [3M/2, 2M)\). This represents a negative integer that wraps around.
- For \(x\), \(Wrap(x) = 1\) (since \(x_{0} + x_{1} \geq M\)), \(MSB(x) = 1\) (since the actual value \(x = x_{0} + x_{1} - M \geq M/2\)). Therefore, \(MW(x) = 2\).
- \(int(x) = x_{0} + x_{1} - 2M = int(y)\)
- For \(y\), since \(x\) is negative, we want \(MSB(y)=1\), so \(y_0 + y_{1} \in [N/2, N) \cup [3N/2, 2N)\).
- For the first case, we have \(int(y) = y_{0} + y_{1} = x_{0} + x_{1} - 2M\). The LHS is in range \([N/2, N)\) but the RHS is in range \([-M/2, 0)\) which is contradictory.
- For the second case, we have \(int(y) = y_{0} + y_{1} - 2N = x_{0} + x_1 - 2M\). So, \(y_{0} + y_{1} = x_{0} + x_{1} + 2(N-M)\).
- We can set \(y_{0} = x_{0} + N-M\) and \(y_{1} = x_{1} + N-M\).
- This gives \(y_{0} + y_{1} = x_{0} + x_{1} + 2(N - M) \in [3M/2 + 2(N-M), 2M + 2(N-M)) = [2N - M/2, 2N + 2M - 2M) = [2N - M/2, 2N)\).
- Since \(y_{0} + y_{1} \geq 2N - M/2 > N\), we get \(Wrap(y) = 1\).
- Hence, \(MW(x) = MW(y) = 2\).
- Multiplication. TODO