Face verification is a powerful technology that confirms an individual’s identity by analyzing facial images. Unfortunately, privacy concerns regarding sensitive facial data arise with the widespread application of face verification. Existing solutions with privacy protection still confront several issues, including system framework, effective computation, and computational efficiency. In this work, we present a fast privacy-preserving solution for multi-client face verification through the threshold Paillier cryptosystem. Specifically, we propose a general framework that supports non-interactive and privacy-preserving face verification for multiple clients. Additionally, we design two secure computing protocols to enable effective privacy-preserving face verification over encrypted data. We also introduce a parallel computing mechanism based on a twin-server architecture, which significantly enhances the efficiency of SAFE. Rigorous privacy analyses indicate that SAFE does not leak any facial data. Extensive experiments demonstrate that SAFE is up to 9 times faster than the state-of-the-art.