Cloud computing will continue flourishing. Like any technology that is widely used and advancing with many benefits, it also comes with issues, some of which are unavoidable. Security is one of the major concerns for cloud computing. To protect user information leakages or system intrusion, the first simple step is to make sure that only legitimate users can access the computing resources. This makes user authentication an important safeguard. There are many approaches to authentication for users in the cloud environments. The password-based authentication is one such technique that is old but is still in use because it is simple. Unfortunately, it is also vulnerable for attack. To alleviate this drawback, recent research has applied provenance to authentication but most do not deal with location. Using a location as part of authentication increasingly becomes necessary, as mobile and wearable technology become a big part of our daily life. This paper presents a new approach to authentication on cloud computing environments. The approach uses data provenance as well as a location of user request. The paper describes the approach, illustrates its use in use case scenarios, and compares its performance with that of the machine-learning model. Using a data synthesized from simulated authentication system, it is shown that the decision tree model has an average of 83.5% accuracy while ours, by relying on theoretical ground, results in 100% accuracy.