Fast secure comparison for medium-sized integers and its application in binarized neural networks

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)

Samenvatting

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 (Formula Presented), the Legendre symbol (Formula Presented) coincides with the sign of x for (Formula Presented), 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 (Formula Presented). 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 (Formula Presented) 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 (Formula Presented)) and 3.8 (for (Formula Presented)) 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.

Originele taal-2Engels
TitelTopics in Cryptology – CT-RSA 2019 - The Cryptographers’ Track at the RSA Conference 2019, Proceedings
RedacteurenMitsuru Matsui
Plaats van productieCham
UitgeverijSpringer
Pagina's453-472
Aantal pagina's20
ISBN van elektronische versie978-3-030-12612-4
ISBN van geprinte versie978-3-030-12611-7
DOI's
StatusGepubliceerd - 1 jan 2019
EvenementCryptographers Track at the RSA Conference 2019, CT-RSA 2019 - San Francisco, Verenigde Staten van Amerika
Duur: 4 mrt 20198 mrt 2019

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11405 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

CongresCryptographers Track at the RSA Conference 2019, CT-RSA 2019
LandVerenigde Staten van Amerika
StadSan Francisco
Periode4/03/198/03/19

Vingerafdruk Duik in de onderzoeksthema's van 'Fast secure comparison for medium-sized integers and its application in binarized neural networks'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Abspoel, M., Bouman, N. J., Schoenmakers, B., & de Vreede, N. (2019). Fast secure comparison for medium-sized integers and its application in binarized neural networks. In M. Matsui (editor), Topics in Cryptology – CT-RSA 2019 - The Cryptographers’ Track at the RSA Conference 2019, Proceedings (blz. 453-472). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11405 LNCS). Springer. https://doi.org/10.1007/978-3-030-12612-4_23