Paper 2023/1684

Nomadic: Normalising Maliciously-Secure Distance with Cosine Similarity for Two-Party Biometric Authentication

Nan Cheng, University of St. Gallen
Melek Önen, EURECOM
Aikaterini Mitrokotsa, University of St. Gallen
Oubaïda Chouchane, EURECOM
Massimiliano Todisco, EURECOM
Alberto Ibarrondo,

Computing the distance between two non-normalized vectors $\mathbfit{x}$ and $\mathbfit{y}$, represented by $\Delta(\mathbfit{x},\mathbfit{y})$ and comparing it to a predefined public threshold $\tau$ is an essential functionality used in privacy-sensitive applications such as biometric authentication, identification, machine learning algorithms ({\em e.g.,} linear regression, k-nearest neighbors, etc.), and typo-tolerant password-based authentication. Tackling a widely used distance metric, {\sc Nomadic} studies the privacy-preserving evaluation of cosine similarity in a two-party (2PC) distributed setting. We illustrate this setting in a scenario where a client uses biometrics to authenticate to a service provider, outsourcing the distance calculation to two computing servers. In this setting, we propose two novel 2PC protocols to evaluate the normalising cosine similarity between non-normalised two vectors 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 function $f$ yielding a binary result with a subsequent binary gate. Overall, our protocols outperform all prior works, requiring only two communication rounds under a strong threat model that also deals with malicious inputs via normalisation. We evaluate our protocols in the setting of biometric authentication using voice, and the obtained results reveal a notable efficiency improvement compared to existing state-of-the-art works.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. Asia CCS 2024
privacy-preservationmalicious securityfunction secret sharingcosine similarity
Contact author(s)
nan cheng @ unisg ch
melek onen @ eurecom fr
aikaterini mitrokotsa @ unisg ch
oubaida chouchane @ eurecom fr
massimiliano todisco @ eurecom fr
ibarrond @ eurecom fr
2024-04-18: last of 3 revisions
2023-10-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nan Cheng and Melek Önen and Aikaterini Mitrokotsa and Oubaïda Chouchane and Massimiliano Todisco and Alberto Ibarrondo},
      title = {Nomadic: Normalising Maliciously-Secure Distance with Cosine Similarity for Two-Party Biometric Authentication},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1684},
      year = {2023},
      doi = {},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.