Cloud computing enables a new paradigm of information and communication resources on demand. Users, enterprises, governments start to consider moving their data into the cloud to enjoy its storage capacity and computation capability. Related data confidentiality, integrity and authentication have been extensively investigated, while newly introduced security concern is not fully addressed, namely, the security of the query results. The cloud storage providers (CSPs) might not be fully trusted and susceptible to be compromised. In addition, the CSPs might deliberately search only part of user data for their own purpose, or they might just be incompetent to carry out complex search requests, which yield incorrect query replies. Therefore, an authentication mechanism of query results is required to enable cloud users not only to protect the security of the data in the cloud, but also to verify the correctness of the query results from the CSPs. In this paper, we propose an efficient authentication scheme for CSPs to provide the proof of a query results and for cloud users to be assured by verifying the proof. We also present extensive security and performance analysis and show that our scheme is secure and efficient for the cloud users.