We build the first sub-linear (in fact, potentially constant-time) public-key searchable encryption system: server can publish a public key PK.anybody can build an encrypted index for document D under PK.client holding the index can obtain a token zw from the server to check if a keyword w belongs to D.search using zw is almost as fast (e.g., sub-linear) as the non-private search.server granting the token does not learn anything about the document D, beyond the keyword w.yet, the token zw is specific to the pair (D, w): the client does not learn if other keywords w′≠ w belong to D, or if w belongs to other, freshly indexed documents D′.server cannot fool the client by giving a wrong token zw. We call such a primitive Encapsulated Search Index (ESI). Our ESI scheme can be made (t, n)-distributed among n servers in the best possible way: non-interactive, verifiable, and resilient to any coalition of up to (t- 1 ) malicious servers. We also introduce the notion of delegatable ESI and show how to extend our construction to this setting. Our solution — including public indexing, sub-linear search, delegation, and distributed token generation — is deployed as a commercial application by a real-world company.