This paper proposes an algorithm to perform privacy-preserving (PP) speaker recognition using Gaussian mixture models (GMM). We consider a scenario where the users have to enrol their voice biometric with the third-party service providers to access different services (i.e., banking). Once the enrolment is done, the users can authenticate themselves to the system using their voice instead of passwords. Since the voice is unique for individuals, storing the users’ voice features at the third-party server raises privacy concerns. Hence, in this paper we propose a novel technique using randomization to perform voice authentication, which allows users to enrol and authenticate their voice in the encrypted domain, hence privacy is preserved. To achieve this, we redesign the GMM to work on encrypted domain. The proposed algorithm is validated using the widely used TIMIT speech corpus. Experimental results demonstrate that the proposed PP algorithm does not degrade the performance compared to the non-PP method and achieve 96.16% true positive rate and 1.77% false positive rate. Demonstration on Android smartphone shows that the algorithm can be executed within two seconds with only 30% of CPU power.