  Face recognition is a widely-used technique for identification or
verification, where a verifier checks whether a face image matches anyone
stored in a database. However, in scenarios where the database is held by a
third party, such as a cloud server, both parties are concerned about data
privacy. To address this concern, we propose CryptoMask, a privacy-preserving
face recognition system that employs homomorphic encryption (HE) and secure
multi-party computation (MPC). We design a new encoding strategy that leverages
HE properties to reduce communication costs and enable efficient similarity
checks between face images, without expensive homomorphic rotation.
Additionally, CryptoMask leaks less information than existing state-of-the-art
approaches. CryptoMask only reveals whether there is an image matching the
query or not, whereas existing approaches additionally leak sensitive
intermediate distance information. We conduct extensive experiments that
demonstrate CryptoMask's superior performance in terms of computation and
communication. For a database with 100 million 512-dimensional face vectors,
CryptoMask offers ${\thicksim}5 \times$ and ${\thicksim}144 \times$ speed-ups
in terms of computation and communication, respectively.
