NOTRY: Deniable messaging with retroactive avowal
Authors: Faxing Wang (University of Melbourne), Shaanan Cohney (University of Melbourne), Riad Wahby (Carnegie Mellon University), Joseph Bonneau (a16z Crypto Research)
Volume: 2024
Issue: 2
Pages: 391–411
DOI: https://doi.org/10.56553/popets-2024-0056
Abstract: Modern secure messaging protocols typically aim to provide deniability. Achieving this requires that convincing cryptographic transcripts can be forged without the involvement of genuine users. In this work, we observe that parties may wish to revoke deniability and avow a conversation after it has taken place. We propose a new protocol called Not-on-the-Record-Yet (NOTRY) which enables users to prove a prior conversation transcript is genuine. As a key building block we propose avowable designated verifier proofs which may be of independent interest. Our implementation in- curs roughly 8× communication and computation overhead over the standard Signal protocol during regular operation. We find it is nonetheless deployable in a realistic setting as key exchanges (the source of the overhead) still complete in just over 1ms on a modern computer. The avowal protocol induces only constant computation and communication performance for the communicating parties and scales linearly in the number of messages avowed for the verifier—in the tens of milliseconds per avowal.
Keywords: proof of non-knowledge, deniable messaging, authenticated key exchange
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
