Grote: Group testing for privacy-preserving face identification

This paper proposes a novel method to perform privacy-preserving face identification based on the notion of group testing, and applies it to a solution using the Cheon-Kim-Kim-Song (CKKS) homomorphic encryption scheme. Securely computing the closest reference template to a given live template requires ?? comparisons, as many as there are identities in a biometric database. Our solution, named Grote, replaces element-wise testing by group testing to drastically reduce the number of such costly, non-linear operations in the encrypted domain from ?? to up to 2√ ??. More specifically, we approximate the max of the coordinates of a large vector by raising to the ??-th power and cumulative sum in a 2D layout, incurring a small impact in the accuracy of the system while greatly speeding up its execution. We implement Grote and evaluate its performance.