IT Companies have shifted their resources to the cloud at rapidly increasing rate. As part of this trend companies are migrating business critical and sensitive data stored in database to cloud-hosted and Database as a Service (DBaaS) solutions.Of all that has been written about cloud computing, precious little attention has been paid to authentication in the cloud. In this paper we have designed a new effective authentication scheme for Cloud Database as a Service (DBaaS). A user can change his/her password, whenever demanded. Furthermore, security analysis realizes the feasibility of the proposed model for DBaaS and achieves efficiency. We also proposed an efficient authentication scheme to solve the authentication problem in cloud. The proposed solution which we have provided is based mainly on improved Needham-Schroeder’s protocol to prove the users’ identity to determine if this user is authorized or not. The results showed that this scheme is very strong and difficult to break it.