This paper presents the design and analysis of the first searchable symmetric encryption (SSE) protocol that supports conjunctive search and general Boolean queries on outsourced symmetrically-encrypted data, and scales to very large databases and arbitrarily-structured data including free text search. Prior SSE constructions focused on single-keyword search and required linear work in the total number of documents, providing limited privacy for structured data. In contrast, the proposed solution provides a realistic trade-off between performance and privacy by efficiently supporting large databases with moderate leakage to the server (in the form of data access patterns, not direct exposure of plaintext data or searched values). The protocol, named OXT, is based on a "virtual" secure two-party protocol where the server holds encrypted pointers to documents, the client holds a list of keywords, and the output is the set of encrypted pointers pointing to documents containing all the client's keywords. The client can then decrypt these pointers to obtain the matching documents, while the server cannot decrypt them or learn the keywords. The protocol is designed to avoid multiple rounds of interaction by precomputing parts of the protocol messages and storing them in encrypted form at the server. OXT supports conjunctive keyword search and general Boolean queries, including negations, disjunctions, threshold queries, and more. It allows for efficient search by scaling with the size of the (estimated) smallest set of documents matching the least frequent keyword in the conjunction. The protocol also supports free text search and combinations of structured data and free text. The security of OXT is analyzed through a formal model that defines a leakage profile, which includes information about the total size of the database, access patterns, and queries, but not the direct exposure of plaintext data or searched values. The protocol is proven secure under an adaptive adversarial model, and its leakage profile is shown to be optimal. OXT is implemented with a focus on efficiency, using DH-type operations over elliptic curves and precomputing parts of the protocol messages. The complexity of the search protocols is independent of the number of documents in the database, and the search complexity scales with the number of documents matching the estimated least frequent keyword in the conjunction. The protocol is tested on large data sets, including the Enron email data set and the ClueWeb09 collection of web pages, demonstrating its scalability and practicality for large databases.This paper presents the design and analysis of the first searchable symmetric encryption (SSE) protocol that supports conjunctive search and general Boolean queries on outsourced symmetrically-encrypted data, and scales to very large databases and arbitrarily-structured data including free text search. Prior SSE constructions focused on single-keyword search and required linear work in the total number of documents, providing limited privacy for structured data. In contrast, the proposed solution provides a realistic trade-off between performance and privacy by efficiently supporting large databases with moderate leakage to the server (in the form of data access patterns, not direct exposure of plaintext data or searched values). The protocol, named OXT, is based on a "virtual" secure two-party protocol where the server holds encrypted pointers to documents, the client holds a list of keywords, and the output is the set of encrypted pointers pointing to documents containing all the client's keywords. The client can then decrypt these pointers to obtain the matching documents, while the server cannot decrypt them or learn the keywords. The protocol is designed to avoid multiple rounds of interaction by precomputing parts of the protocol messages and storing them in encrypted form at the server. OXT supports conjunctive keyword search and general Boolean queries, including negations, disjunctions, threshold queries, and more. It allows for efficient search by scaling with the size of the (estimated) smallest set of documents matching the least frequent keyword in the conjunction. The protocol also supports free text search and combinations of structured data and free text. The security of OXT is analyzed through a formal model that defines a leakage profile, which includes information about the total size of the database, access patterns, and queries, but not the direct exposure of plaintext data or searched values. The protocol is proven secure under an adaptive adversarial model, and its leakage profile is shown to be optimal. OXT is implemented with a focus on efficiency, using DH-type operations over elliptic curves and precomputing parts of the protocol messages. The complexity of the search protocols is independent of the number of documents in the database, and the search complexity scales with the number of documents matching the estimated least frequent keyword in the conjunction. The protocol is tested on large data sets, including the Enron email data set and the ClueWeb09 collection of web pages, demonstrating its scalability and practicality for large databases.