Paper 2018/1236

Fast Secure Comparison for Medium-Sized Integers and Its Application in Binarized Neural Networks

Mark Abspoel, Niek J. Bouman, Berry Schoenmakers, and Niels de Vreede


In 1994, Feige, Kilian, and Naor proposed a simple protocol for secure $3$-way comparison of integers $a$ and $b$ from the range $[0,2]$. Their observation is that for $p=7$, the Legendre symbol $(x | p)$ coincides with the sign of $x$ for $x=a-b\in[-2,2]$, thus reducing secure comparison to secure evaluation of the Legendre symbol. More recently, in 2011, Yu generalized this idea to handle secure comparisons for integers from substantially larger ranges $[0,d]$, essentially by searching for primes for which the Legendre symbol coincides with the sign function on $[-d,d]$. In this paper, we present new comparison protocols based on the Legendre symbol that additionally employ some form of error correction. We relax the prime search by requiring that the Legendre symbol encodes the sign function in a noisy fashion only. Practically, we use the majority vote over a window of $2k+1$ adjacent Legendre symbols, for small positive integers $k$. Our technique significantly increases the comparison range: e.g., for a modulus of $60$ bits, $d$ increases by a factor of $2.9$ (for $k=1$) and $5.4$ (for $k=2$) respectively. We give a practical method to find primes with suitable noisy encodings. We demonstrate the practical relevance of our comparison protocol by applying it in a secure neural network classifier for the MNIST dataset. Concretely, we discuss a secure multiparty computation based on the binarized multi-layer perceptron of Hubara et al., using our comparison for the second and third layers.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision.CT-RSA 2019
multiparty computationsecret sharingsecure comparison
Contact author(s)
M A Abspoel @ cwi nl
2018-12-31: received
Short URL
Creative Commons Attribution


      author = {Mark Abspoel and Niek J.  Bouman and Berry Schoenmakers and Niels de Vreede},
      title = {Fast Secure Comparison for Medium-Sized Integers and Its Application in Binarized Neural Networks},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1236},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.