A facility for performing accurate and real-time privacy-preserving biometrics verification in a client-server environment is described. The facility receives the user's biometrics data such as face, voice, fingerprint, iris, gait, heart rate, etc. The facility then processes and applies various privacy-preserving techniques to this data to complete enrollment and authenticate users, including but not limited to: encrypting data with a key using homomorphic encryption techniques and sending the encryption to the server; the server computes directly on the encryption and returns the result, which is also encrypted under the same key, to the client; the client optionally performs post-processing and decryption (in any order) and obtains the enrollment or authentication result. The facility may repeat this process to increase security level, resulting in more than 1 round trip between the client and the server. Lastly, the facility employs methods that generalize to other privacy-preserving applications beyond biometrics verification.