Abstract
In this paper we introduce Password Authenticated Keyword Search (PAKS), a cryptographic scheme where any user can use a single human-memorizable password to outsource encrypted data with associated keywords to a group of servers and later retrieve this data through the encrypted keyword search procedure. PAKS ensures that only the legitimate user who knows the initially registered password can perform outsourcing and retrieval of the encrypted data. In particular, PAKS guarantees that no single server can mount an offline attack on the user's password or learn any information about the encrypted keywords. The concept behind PAKS protocols extends previous concepts behind searchable encryption by removing the requirement on the client to store high-entropy keys, thus making the protocol device-agnostic on the user side. In this paper we model three security requirements for PAKS schemes (indistinguishability against chosen keyword attacks, authentication and consistency) and propose an efficient direct construction in a two-server setting those security we prove in the standard model under the Decisional Diffie-Hellman assumption. Our efficiency comparison shows that the proposed scheme is practical and offers high performance in relation to computations and communications on the user side.