This paper presents secure conjunctive keyword search over encrypted data. The authors study the scenario where a user stores encrypted documents on an untrusted server and needs to retrieve documents that meet certain search criteria. Previous work has focused on single keyword searches, but conjunctive keyword search (searching for multiple keywords simultaneously) requires more sophisticated solutions. The authors define a security model for conjunctive keyword search over encrypted data and present the first secure schemes for conducting such searches. The first scheme has a communication cost linear in the number of documents, but this cost can be incurred offline. The security of this scheme relies on the Decisional Diffie-Hellman (DDH) assumption. The second scheme has a communication cost proportional to the number of keyword fields and relies on a new hardness assumption. The paper discusses the limitations of existing schemes, which only allow the server to identify documents matching a single keyword, but not boolean combinations of queries. Boolean combinations are essential for effective document retrieval, as simple keyword searches often yield too coarse results. For example, a user might want to retrieve emails from Bob that are urgent and related to finance, requiring the ability to search on the conjunction of keywords "Bob", "urgent", and "finance". The authors propose protocols that allow for conjunctive keyword queries on encrypted data. Although such searches do not encompass all possible search criteria, they are a crucial building block, as indicated by the reliance of today's web search engines on conjunctive search. The paper also briefly reviews two simple solutions to conjunctive search - set intersection and meta-keywords - and explains why they are unsatisfactory.This paper presents secure conjunctive keyword search over encrypted data. The authors study the scenario where a user stores encrypted documents on an untrusted server and needs to retrieve documents that meet certain search criteria. Previous work has focused on single keyword searches, but conjunctive keyword search (searching for multiple keywords simultaneously) requires more sophisticated solutions. The authors define a security model for conjunctive keyword search over encrypted data and present the first secure schemes for conducting such searches. The first scheme has a communication cost linear in the number of documents, but this cost can be incurred offline. The security of this scheme relies on the Decisional Diffie-Hellman (DDH) assumption. The second scheme has a communication cost proportional to the number of keyword fields and relies on a new hardness assumption. The paper discusses the limitations of existing schemes, which only allow the server to identify documents matching a single keyword, but not boolean combinations of queries. Boolean combinations are essential for effective document retrieval, as simple keyword searches often yield too coarse results. For example, a user might want to retrieve emails from Bob that are urgent and related to finance, requiring the ability to search on the conjunction of keywords "Bob", "urgent", and "finance". The authors propose protocols that allow for conjunctive keyword queries on encrypted data. Although such searches do not encompass all possible search criteria, they are a crucial building block, as indicated by the reliance of today's web search engines on conjunctive search. The paper also briefly reviews two simple solutions to conjunctive search - set intersection and meta-keywords - and explains why they are unsatisfactory.