Fast and Private 1-to-$N$ Face Identification Protocols

Face identification is a pivotal aspect of user authentication across diverse domains, spanning from smartphone security to access control in high-security environments. Privacy-preserving face identification aims to authenticate users using facial images while preserving their privacy. In this paper, we focus on privacy-preserving protocols for one-to-many (1-to-<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$N$</tex-math></inline-formula>) face identification. Such protocols enable the authentication of individuals from a pool of registered users without disclosing their identity among the group. We present new protocols based on secret-sharing based secure multi-party computation (MPC). Our initial (warm-up) protocol directly applies MPC to the plain ArcFace framework, marking the first instance of such a face identification scheme without reliance on homomorphic encryption, a primary tool in previous works. Notably, this protocol exhibits efficiency for small-scale databases, requiring approximately 1 second for authentication among 1000 users. Building upon this foundation, our main contribution lies in our second protocol, designed to enhance scalability via a new approach to operations on large-scale databases. It significantly improves runtime performance compared to the state-of-the-art scheme of Bai et al., achieving approximately 2.31 times, 4.59 times, and 6.80 times faster authentication for registered user databases of sizes <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$N\mathalpha {=}10\mathalpha {,}000$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$N\mathalpha {=}100\mathalpha {,}000$</tex-math></inline-formula>, and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$N\mathalpha {=}1\mathalpha {,}000\mathalpha {,}000$</tex-math></inline-formula>, respectively. Notably, our protocol enables user authentication in about a second for the first time in the case of database with 30,000 users. While our second protocol offers fast authentication times, it does entail some leakage of intermediate values. Nevertheless, this leakage is minimal and far less than that of previous works that allow leakage. Through our contributions, we aim to propel the state-of-the-art in face identification protocols, striking a balance between the imperatives of efficiency and privacy in real-world applications.