Funshade: Function Secret Sharing for Two-Party Secure Thresholded Distance Evaluation
Authors: Alberto Ibarrondo (Copper.co), Hervé Chabanne (Idemia & Telecom Paris), Melek Önen (EURECOM)
Volume: 2023
Issue: 4
Pages: 21–34
DOI: https://doi.org/10.56553/popets-2023-0096
Abstract: We propose a novel privacy-preserving, two-party computation of various distance metrics (e.g., Hamming distance, Scalar Product) followed by a comparison with a fixed threshold, which is known as one of the most useful and popular building blocks for many different applications including machine learning, biometric matching, etc. Our solution builds upon recent advances in function secret sharing and makes use of an optimized version of arithmetic secret sharing. Thanks to this combination, our new solution named Funshade is the first to require only one round of communication and two ring elements of communication in the online phase, outperforming all prior state-of-the-art schemes while relying on lightweight cryptographic primitives. Lastly, we implement our solution from scratch in portable C and expose it in Python, testifying its high performance by running secure biometric identification against a database of 1 million records in ~10 seconds with full correctness and 32-bit precision, without parallelization.
Keywords: Function Secret Sharing, Secure Two Party Computation, Scalar Product, Hamming Distance
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
