As nowadays most web application requests originate from mobile devices, authentication of mobile users is essential in terms of security considerations. To this end, recent approaches rely on machine learning techniques to analyze various aspects of user behavior as a basis for authentication decisions. These approaches face two challenges: first, examining behavioral data raises significant privacy concerns, and second, approaches must scale to support a large number of users. Existing approaches do not address these challenges sufficiently. We propose mPSAuth, an approach for continuously tracking various data sources reflecting user behavior (e.g., touchscreen interactions, sensor data) and estimating the likelihood of the current user being legitimate based on machine learning techniques. With mPSAuth, both the authentication protocol and the machine learning models operate on homomorphically encrypted data to ensure the users' privacy. Furthermore, the number of machine learning models used by mPSAuth is independent of the number of users, thus providing adequate scalability. In an extensive evaluation based on real-world data from a mobile application, we illustrate that mPSAuth can provide high accuracy with low encryption and communication overhead, while the effort for the inference is increased to a tolerable extent.