Efficient Cryptographic Password Hardening Services from Partially Oblivious Commitments

Password authentication still constitutes the most widespread authentication concept on the Internet today, but the human incapability to memorize safe passwords has left this concept vulnerable to various attacks ever since. Affected enterprises such as Facebook now strive to mitigate such attacks by involving external cryptographic services that harden passwords. Everspaugh et al. provided the first comprehensive formal treatment of such a service, and proposed the Pythia PRF-Service as a cryptographically secure solution (Usenix Security'15). Pythia relies on a novel cryptographic primitive called partially oblivious pseudorandom functions and its security is proven under a strong new interactive assumption in the random oracle model. In this work, we prove that this strong assumption is inherently necessary for the Pythia construction, i.e., it cannot be weakened without invalidating the security of Pythia. More generally, it is impossible to reduce the security of Pythia to any non-interactive assumptions. Hence any efficient, scalable password hardening service that is secure under weaker assumptions necessarily requires a conceptually different construction. To this end, we propose a construction for password hardening services based on a novel cryptographic primitive called partially oblivious commitments, along with an efficient secure instantiation based on simple assumptions. The performance and storage evaluation of our prototype implementation shows that our protocol runs almost twice as fast as Pythia, while achieving a slightly relaxed security notion but relying on weaker assumptions.