Paper 2011/539

Sign Modules in Secure Arithmetic Circuits

Ching-Hua Yu

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
multi-party computationarithmetic black-boxunconditionally secure comparison
Contact author(s)
chinghua yu @ gmail com
History
2013-02-16: last of 3 revisions
2011-10-03: received
See all versions
Short URL
https://ia.cr/2011/539
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/539,
      author = {Ching-Hua Yu},
      title = {Sign Modules in Secure Arithmetic Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2011/539},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/539}},
      url = {https://eprint.iacr.org/2011/539}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.