Paper 2026/2794

BeaverDam: A Post-Quantum Threshold Key Recovery Protocol from a One-Time Threshold Oblivious Random Function

Abstract

Secure backups are a practical necessity of E2EE messaging apps, typically relying on password-protected key-recovery (PPKR) protocols. These allow users to turn a human-memorable password into a cryptographic key with the help of a server. Recently, Signal and Juicebox proposed threshold PPKR (tPPKR) protocols, removing the trust on a centralized server. Unfortunately, known solutions are only classically secure, lagging behind the shift toward post-quantum (PQ), or to be more precise, hybrid secure E2EE. We present BeaverDam, a novel tPPKR protocol that is PQ secure with efficiency close to existing classical protocols. It also easily extends to hybrid security, standing as the first concretely efficient hybrid-secure tPPKR protocol. BeaverDam relies on a new primitive we introduce --- one-time threshold oblivious random functions (tORF). Unlike full-fledged OPRFs, which are notoriously difficult to construct in a PQ-secure manner, one-time tORF offers weaker but sufficient security guarantees tailored to the tPPKR setting. We then construct an efficient one-time tORF called Beaver, inspired by multi-party computation (MPC) techniques. Owing to the one-time feature, we only need to securely compute a 2-wise independent hash function, making our protocol very efficient. We conclude by presenting a practical instantiation of BeaverDam and comparing its performance to state-of-the-art classical tPPKR protocols, namely Signal's SVR3 and Juicebox.