Paper 2026/522

X3DH with Deniable Authentication without Trusted Third Parties

Abstract

Message Authentication in the Short Authenticated String model (SAS-MA) allows Alice and Bob to establish a secure channel without trust in any third party, as long as they can exchange short authenticated strings, e.g. 20 bits. In a recent paper, Gu et al. [17] showed a SAS-MA scheme based on Verifiable Random Functions (VRF), which can utilize the ephemeral keys sent in the X3DH Authenticated Key Exchange (AKE), allowing for extending X3DH to SAS-MA with minimal round complexity and no changes to X3DH key distribution. X3DH is used in many messaging apps, including WhatsApp and Signal, and a SAS-MA extension of X3DH would allow app users to authenticate their connections without trust in PKI or the app’s Key Distribution Center (KDC), as long as they can exchange short authenticated strings (SAS), using out of band authenticated channels. However, a major motivation behind using X3DH as an AKE is its deniability property, i.e. that an X3DH transcript cannot serve as a proof that either Alice or Bob established a secure connection with each other. The VRF-based SAS-MA extension of X3DH of [17] violates deniability, essentially because a VRF is a signature. We show an alternative SAS-MA scheme which offers the same ease of integration with X3DH as the VRF-based SAS-MA of [17], but it (almost) maintains the deniability of X3DH. The proposal is based on a private VRF (PVRF), which allows only ‘designated-verifier’ verification of correctness. We show a low-cost PVRF variant of ECVRF, and we show that X3DH extended by our PVRF-based SAS-MA adds human-centric no-trust-in-KDC authentication to X3DH while preserving the deniability properties of X3DH.