Paper Info
Title
Fast Secure Comparison for Medium-Sized Integers and Its Application in Binarized Neural Networks.
Abstract
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 (left( xmid pright) ) coincides with the sign of x for (x=a-bin [-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.8 (for (k=1)) and 3.8 (for (k=2)) respectively. We give a practical method to find primes with suitable noisy encodings.
Year
DOI
Venue
2019
10.1007/978-3-030-12612-4_23
IACR Cryptology ePrint Archive
DocType
Volume
Citations 
Conference
2018
0
PageRank 
References 
Authors
0.34
6
4
Name
Order
Citations
PageRank
Mark Abspoel101.35
Niek Bouman2305.50
Berry Schoenmakers31550119.18
Niels de Vreede482.57