Searchable symmetric encryption (SSE) allows a party to outsource the storage of his data

to another party (a server) in a private manner, while maintaining the ability to selectively

search over it. This problem has been the focus of active research for over a decade. In

recent years, efficient solutions requiring only a constant number of rounds of interaction

have been proposed at the expense of providing weaker security guarantees – specifically,

these solutions allow the “access pattern” (i.e., the order in which the encrypted items

are “touched” by the server) to be revealed. In this talk we consider this weaker security

model as well, and show two constant-round solutions to SSE that simultaneously enjoy

the following properties:

1) Both solutions are more efficient than previous constant-round schemes. In particular, the work performed by the server per returned document is constant as opposed to

linear in the size of the data.

2) Both solutions enjoy stronger security guarantees than previous constant-round

schemes. We point out shortcomings of previous notions of security for SSE, and show

how to design constructions which avoid these pitfalls. Further, our second solution also

achieves what we call adaptive SSE security, where queries into the database can be chosen

adaptively (by the adversary) during the execution of the search. We also consider multi-user SSE, where an arbitrary group of parties other than the

owner can submit search queries. We formally define SSE in the multi-user setting, and

present an efficient construction that achieves better performance than simply using access

control mechanisms.