International Association
for Cryptologic Research

We investigate how users of instant messaging (IM) services can acquire strong encryption keys to back up their messages and media with strong cryptographic guarantees. Many IM users regularly change their devices and use multiple devices simultaneously, ruling out any long-term secret storage. Extending the end-to-end encryption guarantees from just message communication to also incorporate backups has so far required either some trust in an IM or outsourced storage provider, or use of costly third-party encryption tools with unclear security guarantees. Recent works have proposed solutions for password-protected key material, however all require one or more servers to generate and/or store per-user information, inevitably invoking a cost to the users.

We define distributed key acquisition (DKA) as the primitive for the task at hand, where a user interacts with one or more servers to acquire a strong cryptographic key, and both user and server are required to store as little as possible. We present a construction framework that we call PERKS---Password-based Establishment of Random Keys for Storage---providing efficient, modular and simple protocols that utilize Oblivious Pseudorandom Functions (OPRFs) in a distributed manner with minimal storage by the user (just the password) and servers (a single global key for all users). Along the way we introduce a formal treatment of DKA, and provide proofs of security for our constructions in their various flavours. Our approach enables key rotation by the OPRF servers, and for this we incorporate updatable encryption. Finally, we show how our constructions fit neatly with recent research on encrypted outsourced storage to provide strong security guarantees for the outsourced ciphertexts.