15. A system, comprising: a computing device; and a computer-readable storage device coupled to the computing device and having instructions stored thereon which, when executed by the computing device, cause the computing device to perform operations for using searchable encryption to query a database storing encrypted data, the operations comprising: executing at least a portion of a searchable encryption scheme that provides an asymptotically optimal sub-linear search time and comprises probabilistic operations to generate a set of search indices and a search token; receiving the set of search indices; receiving the search token, and in response: searching at least one search index of the set of search indices based on the search token, and determining that the at least one search index corresponds to an initial setup protocol, wherein the at least one search index comprises an empty table that is absent an entry and is absent a search history of previously submitted search tokens corresponding to the search token, and in response, receiving one or more identifiers, each identifier being associated with a respective ciphertext comprising an access pattern that is determined to be responsive to the search token, and updating the at least one search index to comprise the entry based on the search token and the one or more identifiers and to comprise the search history of the search token by using an inverted index for the search token; and transmitting search results, the search results comprising the one or more ciphertexts that are determined to be responsive to the search token.
15. A system, comprising: a computing device; and a computer-readable storage device coupled to the computing device and having instructions stored thereon which, when executed by the computing device, cause the computing device to perform operations for using searchable encryption to query a database storing encrypted data, the operations comprising: executing at least a portion of a searchable encryption scheme that provides an asymptotically optimal sub-linear search time and comprises probabilistic operations to generate a set of search indices and a search token; receiving the set of search indices; receiving the search token, and in response: searching at least one search index of the set of search indices based on the search token, and determining that the at least one search index corresponds to an initial setup protocol, wherein the at least one search index comprises an empty table that is absent an entry and is absent a search history of previously submitted search tokens corresponding to the search token, and in response, receiving one or more identifiers, each identifier being associated with a respective ciphertext comprising an access pattern that is determined to be responsive to the search token, and updating the at least one search index to comprise the entry based on the search token and the one or more identifiers and to comprise the search history of the search token by using an inverted index for the search token; and transmitting search results, the search results comprising the one or more ciphertexts that are determined to be responsive to the search token. 20. The system of claim 15 , wherein the search token comprises an encrypted keyword.