## 3 Communication-Efficient Secure Batch Division  
An important prerequisite for computing statistical tests securely is secure division. There are two main algorithms that are used for division--Newton-Raphson and Goldschmidt. However, the Goldschmidt division (given below in Algorithm 1) is usually preferred as the multiplications in each iteration can be done concurrently [18]. Moreover, the Newton-Raphson method can only be used to calculate the inverse of the divisor with the dividend being multiplied in the end to calculate the result. The Goldschmidt method, on the other hand, is able to directly calculate the result, thus reducing the multiplicative depth, which is a crucial consideration in the context of MHE. [PERSON]'s division algorithm begins with a \"good\" initial approximation and iteratively improves upon the approximation. Specifically, a \"good\" initial approximation is defined as an approximation with relative error \(\epsilon_{0}=1-bw_{0}<1\) and it can be shown through induction that after \(t\) iterations, \(a_{t}\) has relative error \(\epsilon_{0}^{2^{t}}\)[18], which makes this a very efficient method. ```
0:\(a,b,T,w_{0}\) s.t. \(w_{0}\) is a \"good\" initial approximation to \(\frac{1}{b}\)
0:\(c\approx\frac{a}{b}\) \(a_{0}\gets a\) \(b_{0}\gets w_{0}\) \(i\gets 0\) while\(i<T\)do \(a_{i+1}\gets a_{i}w_{i}\) \(b_{i+1}\gets b_{i}w_{i}\) \(w_{i+1}\gets 2-b_{i+1}\) \(i\gets i+1\) endwhile return\(c=a_{T}\)
```  
**Algorithm 1** Goldschmidt division  
Traditionally, in a SMPC setting, the initial approximation is obtained by normalizing the denominator to the range \((0.5,1]\), where a well known \"good\" initial approximation exists (\(w_{0}=2.9142-2b\), \(\epsilon_{0}<0.08578\)) [18]. The normalization is done through the use of advanced operations such as [PERSON] et al. 's secure bit decomposition protocol [19]. However, in MHE, efficient secure bit decomposition protocols are not known to exist, which forces us to obtain the initial approximation through other means. Our solution is to relax the problem and assume that the denominator is known to exist in some arbitrary range \([b_{\ell},b_{u}]\). This is a safe assumption in the context of statistical tests where the input variables are typically bounded, thus allowing us to compute the bounds for the denominator as was the case for both our target applications of [PERSON]'s \(t\) test and \(\chi^{2}\) test (see Section 4). Assuming that the denominator is in some arbitrary range, we then construct a \"good\" initial approximation by utilizing optimal initial approximations that minimize the relative error of the initial approximation, which have been published by [PERSON] et al. [20]. It can be shown that for a given denominator \(b\in[b_{\ell},b_{u}]\), the approximation \(w_{0}=\frac{-8}{b_{\ell}^{2}+6b_{\ell}b_{u}+b_{u}^{2}}b+\frac{8(b_{\ell}+b_{u} )}{b_{\ell}^{2}+6b_{\ell}b_{u}+b_{u}^{2}}\) minimizes the relative error \(\epsilon_{0}=\frac{(b_{u}-b_{\ell})^{2}}{b_{\ell}^{2}+6b_{\ell}b_{u}+b_{u}^{ 2}}=\frac{b_{\ell}^{2}-2b_{\ell}b_{u}+b_{u}^{2}}{b_{\ell}^{2}+6b_{\ell}b_{u}+b _{u}^{2}}<1\), which satisfies the constraint for a \"good\" initial approximation for the Goldschmidt algorithm as well. One important consideration in utilizing this method is that since we may not have tight bounds on the denominator, the algorithm can take a large number of iterations--taking more than 10 iterations for denominators in the range \([1,1\times 10^{4}]\)--unlike the SMPC method, which can finish within 2 iterations after normalization. While this theoretically results in a high multiplicative depth circuit, we leverage the lightweight collective bootstrapping protocol presented by [PERSON] et al. [17] to trade off some communication cost for computational efficiency. Additionally, by leveraging the Single Instruction Multiple Data (SIMD) property of MHE, our method allows us to compute an entire batch of divisions in one go, thus resulting in much lower communication costs compared to performing a similar batch of divisions in SMPC.