Helger Lipmaa's publications

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.


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


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