## Secure Equality and Greater-Than Tests with Sublinear Online Complexity

Helger Lipmaa and Tomas Toft. Secure Equality and Greater-Than Tests with Sublinear Online Complexity. In Fedor V. Fomin, Rusins Freivalds, Marta Kwiatkowska and David Peleg, editors, *ICALP 2013*, volume 7966 of *Lecture Notes in Computer Science*, pages 645--656, Riga, Latvia, July 8--12, 2013. Springer, Heidelberg.

**File:**
[.pdf (357 KB)] __pdf recommended__.

**Abstract**:

Secure multiparty computation (MPC) allows multiple parties to
evaluate functions without disclosing the private inputs. Secure comparisons
(testing equality and greater-than) are important primitives required by
many MPC applications. We propose two equality tests for $\ell$-bit values
with $O(1)$ online communication that require $O(\ell)$ respectively
$O(\kappa)$ total work, where $\kappa$ is a correctness parameter.
Combining these with ideas of Toft~\cite{PKC2011:Toft}, we obtain (i) a
greater-than protocol with sublinear online complexity in the arithmetic
black-box model ($O(c)$ rounds and $O(c\cdot\ell^{1/c})$ work online, with
$c = \log \ell$ resulting in logarithmic online work). In difference to
Toft, we do not assume two mutually incorruptible parties, but $O(\ell)$
offline work is required, and (ii) two greater-than protocols with the same
online complexity as the above, but with overall complexity reduced to
$O(\log\ell(\kappa+\log\log\ell))$ and $O(c\cdot\ell^{1/c}
(\kappa+\log\ell))$; these require two mutually incorruptible parties, but
are highly competitive with respect to online complexity when compared to
existing protocols.

**Keywords:** Additively homomorphic encryption, arithmetic black box, secure comparison, secure equality test.

**Comment:**
Abstract corresponds to prefinal version

**Authors:**

Page by Helger Lipmaa. Send your inqueries to `<helger.lipmaa>gmail.com`.