International Association
for Cryptologic Research

Computing $\Delta(\mathbfit{x},\mathbfit{y}) \geq \tau$, the distance between two vectors $\mathbfit{x}$ and $\mathbfit{y}$ chained with a comparison to a predefined public threshold $\tau$, is an essential functionality that is extensively used in privacy-sensitive applications such as biometric authentication and identification, machine learning algorithms ({\em e.g.,} linear regression, k-nearest neighbors etc.) or typo-tolerant password-based authentication. Cosine similarity is one of the most popular distance metrics employed in these settings. In this paper, we investigate the privacy-preserving computation of cosine similarity in a two-party distributed setting {\em i.e.,} where a client outsources the distance calculation to two servers, while revealing only the result of the comparison to the service provider. We propose two two-party computation (2PC) protocols of cosine similarity followed by comparison to a public threshold, one in the semi-honest and one in the malicious setting. Our protocols combine additive secret sharing with function secret sharing, saving one communication round by employing a new building block to compute the composition of a bit and a binary function $f$, thus requiring only two communication rounds under a strong threat model. We evaluate our protocols in the setting of biometric authentication using voice biometrics. Our results show that not only are the proposed protocols efficient, but they also maintain the same accuracy as the plain-text systems.