Fast Secure Comparison for Medium-Sized Integers and Its Application in Binarized Neural Networks
Fast Secure Comparison for Medium-Sized Integers and Its Application in Binarized Neural Networks
复制标题
DOI：
10.1007/978-3-030-12612-4_23
复制
发表时间：
2019-03
期刊：
影响因子：
--
通讯作者：
Mark Abspoel;N. Bouman;Berry Schoenmakers;N. Vreede
中科院分区：
文献类型：
--
作者：
Mark Abspoel;N. Bouman;Berry Schoenmakers;N. Vreede
1994 年，Feige、Kilian 和 Naor 提出了一个简单的协议，用于对 [0, 2] 范围内的整数 a 和 b 进行安全三向比较。他们的观察是，勒让德符号与 xfor 的符号一致，从而减少了对勒让德符号的安全评估的安全比较。最近，在 2011 年，Yu 将这个想法推广到处理更大范围 [0,d] 的整数的安全比较，本质上是通过搜索勒让德符号与符号函数 on 重合的素数。在本文中，我们提出了基于勒让德符号的新比较协议，该协议还采用了某种形式的纠错。我们通过要求勒让德符号仅以噪声方式对符号函数进行编码来放松素数搜索。实际上，对于小正整数sk，我们对相邻勒让德符号的窗口使用多数投票。我们的技术显着增加了比较范围：例如，对于 60 位的模数，分别减少了 2.8 倍和 3.8 倍。我们给出了一种实用的方法来查找具有合适噪声编码的素数。我们通过将比较协议应用于 MNIST 数据集的安全神经网络分类器来证明其实际相关性。具体而言，我们使用第二层和第三层的比较，讨论基于 Hubara 等人的二值化多层感知器的安全多方计算。
In 1994, Feige, Kilian, and Naor proposed a simple protocol for secure 3-way comparison of integersaandbfrom the range [0, 2]. Their observation is that for, the Legendre symbolcoincides with the sign ofxfor, 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. 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 ofadjacent Legendre symbols, for small positive integersk. Our technique significantly increases the comparison range: e.g., for a modulus of 60 bits,dincreases by a factor of 2.8 (for) and 3.8 (for) 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.