Square root implementation

[manel1874]

I have two questions:

1. Does your _isqrt implementation follow this bit-decomposition approach?

mpyc/mpyc/statistics.py

Line 182 in b8d2d5d

def _isqrt(a):

2. Do you have any idea about the trade-offs between your secure bitwise approach and the SCALA-MAMBA implementation (sec 14.7) that is based on both [L12] and [ABZS12]? The SCALA-MAMBA approach seems heavier. Do you have any intuition on that?

mpyc/mpyc/statistics.py

Line 200 in b8d2d5d

def _fsqrt(a):

---

[L12] Secure Distributed Computation of the Square Root and Applications

[ABZS12] Secure Computation on Floating Point Numbers

[lschoe]

You asking these questions at the right time, especially Q2;)

For Q1, the answer is yes indeed. However, I would not refer to it as a "bit decomposition approach" because a main benefit is that the use of a bit decomposition is avoided. The result is computed bit-by-bit though, and accumulated in a secure integer. The running time is dominated by the $\ell/2$ secure comparisons, which are executed sequentially. That may be acceptable, if this function isn't evaluated frequently. The approach is well-known, often used as a programming exercise, and for secure computation it is easy to make it oblivious (constant-time).

For Q2, we have this paper Divisions and Square Roots with Tight Error Analysis from Newton–Raphson Iteration in Secure Fixed-Point Arithmetic which got published just the other day. It also includes protocols for (integer) square roots, and the plan is to include these in MPyC as well. The paper by Liedel [L12] is also discussed briefly. Approaches using secure floating-point arithmetic like [ABZS12] are usually not performing that well, is my first guess. Overall, we get $O(\log \ell)$ round complexity for the basic functions like (integer) square roots in our paper.

[manel1874]

Oh! Great timing in fact.

I will take a look more closely to the paper. But it seems that in the paper you don't mention/compare that bit-by-bit approach with your proposal. Do you have any idea how your new approach and the secure bit-by-bit approach compare to each other?

[manel1874]

I've been going through your paper on division and square roots and I cannot find a reference for the $[[v]] \leftarrow \mathbf{Scale}([[a]])$ protocol. Could you provide some more information? Thanks you!

[lschoe]

A common way to implement Scale([[a]]) is via the secure bit decomposition of a, looking for the most significant bit of a in an oblivious manner.

[lschoe]

So the bit-by-bit approach uses $\ell/2$ sequential secure comparisons. A secure comparison can theoretically be done in $O(1)$ rounds but that's often of no practical significance, and one is better off using just a $\log_2\ell$ rounds approach. This works out as $\frac{\ell}{2} \log_2\ell$ rounds.

And the Newton--Raphson approach takes $O(\log\ell)$ rounds overall, which looks favorable. But there are hidden constants here, and there is also the total number of secure multiplications required.

I think the bit-by-bit approach is favorable for small values of $\ell$. To work out the cutoff point one would experiment, and even then one should wonder about the varying conditions, like roundtrip time vs computing speed. Ultimately, one may include several regimes in the code and switch between these heuristically. Like in the mpc.is_zero() function:

mpyc/mpyc/runtime.py

Lines 1304 to 1312 in b8d2d5d

	def is_zero(self, a):
	"""Secure zero test a == 0."""
	if isinstance(a, self.SecureFiniteField):
	return 1 - self.pow(a, a.field.order - 1)
	if a.bit_length/2 > self.options.sec_param >= 8 and a.field.order%4 == 3:
	return self._is_zero(a)
	return self.sgn(a, EQ=True)