In this paper, we present a secure framework when the location information of mobile terminals is utilized in a cloud computing environment. Because cloud computing provides powerful storage capability and scalability, many application providers start migrating the data stored in their original databases to outsourced databases (ODB), such as AMAZON SIMPLEDB. However, because of the multiple tenants and multiple replicas of data in the cloud databases, the security issues of location-based services (LBS) become more serious in cloud computing. In this paper, we propose a security model for LBS using ODB and demonstrate how we can use distributed storage and international mobile subscriber identity (IMSI) as user identification to secure the location data. Enhanced privacy and authentication mechanisms on top of the suggested security framework are also proposed, which achieve significant improvements in privacy, authentication, and continuity when providing LBS in cloud computing. Simulation results show that network coding scheme has better performance than hash function scheme.