This paper presents the first searchable symmetric encryption (SSE) protocol that supports conjunctive search and general Boolean queries on outsourced symmetrically-encrypted data, scaling to very large databases and arbitrarily-structured data, including free text search. The protocol provides a practical trade-off between performance and privacy by allowing moderate leakage to the outsourced server in the form of data access patterns, without exposing plaintext data or searched values. The authors provide a detailed cryptographic analysis of the privacy and security of their protocols, establishing precise upper bounds on the allowed leakage. They demonstrate the practicality of their approach through performance results on a prototype applied to large data sets, including encrypted search over the English Wikipedia. The paper also discusses the challenges of large databases and imperfect security, and introduces a new primitive called a *tuple set* (T-set) to enable efficient and secure search on structured and unstructured data. The main contribution is the OXT protocol, which supports arbitrary Boolean queries and achieves sub-linear search complexity in the size of the smallest term in the conjunction. The security of OXT is formally analyzed, showing that it leaks only the specified leakage profile.This paper presents the first searchable symmetric encryption (SSE) protocol that supports conjunctive search and general Boolean queries on outsourced symmetrically-encrypted data, scaling to very large databases and arbitrarily-structured data, including free text search. The protocol provides a practical trade-off between performance and privacy by allowing moderate leakage to the outsourced server in the form of data access patterns, without exposing plaintext data or searched values. The authors provide a detailed cryptographic analysis of the privacy and security of their protocols, establishing precise upper bounds on the allowed leakage. They demonstrate the practicality of their approach through performance results on a prototype applied to large data sets, including encrypted search over the English Wikipedia. The paper also discusses the challenges of large databases and imperfect security, and introduces a new primitive called a *tuple set* (T-set) to enable efficient and secure search on structured and unstructured data. The main contribution is the OXT protocol, which supports arbitrary Boolean queries and achieves sub-linear search complexity in the size of the smallest term in the conjunction. The security of OXT is formally analyzed, showing that it leaks only the specified leakage profile.