Paper 2011/539 Original: eprint.iacr.org/2011/539 ↗

Sign Modules in Secure Arithmetic Circuits

Abstract

In 1994, Feige, Killian, and Naor suggested a toy protocol of secure comparison, which takes secret input $[x]_7$ and $[y]_7$ between 0 and 2, using the modulo 7 arithmetic circuit. Because 0, 1, and 2 are quadratic residues while 5 and 6 are non-residues modulo 7, the protocol is done by securely evaluating the Legendre symbol of $[x-y]_7$, which can be carried out very efficiently by $O(1)$ secure multiplication gates. However, the extension regarding computation in large fields is undiscussed, and furthermore, whether it is possible to turn a toy comparison into a practically usable protocol is unknown. Motivated by these questions, in this paper, we study secure comparison-related problems using only the secure arithmetic black-box of a finite field, counting the cost by the number of secure multiplications. We observe that a specific type of quadratic patterns exists in all finite fields, and the existence of these patterns can be utilized to explore new solutions with sublinear complexities to several problems. First, we define \emph{sign modules} as partial functions that simulate integer signs in an effective range using a polynomial number of arithmetic operations in a finite field. Let $\ell$ denote the bit-length of a finite field size. We show the existence of $\fr{\ell/5}$-``effective" sign modules in any finite field that has a sufficiently large characteristic. When $\ell$ is decided first, we further show (by a constructive proof) the existence of prime fields that contain an $\Omega(\ell\log \ell)$-``effective" sign module and propose an efficient polynomial-time randomized algorithm that finds concrete instances of sign modules. Then, based on one effective sign module in an odd prime field $\Z_p$ and providing a binary-expressed random number in $\Z_p$, prepared in the offline phase, we show that the computation of bitwise less-than can be improved from the best known result of $O(\ell)$ to $O(\sqrt{\frac{\ell}{\log \ell}})$ (with $O(1)$ rounds) in the online phase using only the $\Z_p$-arithmetic black-box. Accompanied by several related improvements, secure computation involving integer comparisons and modular reductions can be improved from the best known result $O(\ell)$ to $O(\sqrt{\frac{\ell}{\log \ell}})$ (with $O(1)$ rounds), and a (deterministic) zero test can be improved from $O(\ell)$ to $O(1)$ in the online phase. Additionally, a linear complexity of bit-decomposition is also obtained.