With the growth in the popularity of cloud storage service (CSS), the accumulation of private data on the cloud requires the use of data encryption to prevent leakage of sensitive information to untrusted third parties. However, as the amount of data kept on the cloud storage is increasing, the use of data encryption makes it difficult or even impossible to locate the data of interest efficiently and securely. In this paper, we present a framework for CSS to support queries in encrypted form so that the data on cloud storage can be located efficiently and securely. At the core of the framework is a novel indexing structure, called the bloom filter encrypted search tree (BFEST). The BFEST supports queries in the form of phrase keywords. Client-side encryption, using secret keys that are unknown to the cloud service provider, protects the queries and the retrieved data. We implemented a prototype by extending the hicloud S3 [13] CSS with the proposed framework. The experimental results indicate that the framework can ensure query privacy for encrypted data with an acceptable performance overhead in a practical setting.