Paper 2023/1926

NOTRY: deniable messaging with retroactive avowal

Faxing Wang, University of Melbourne
Shaanan Cohney, University of Melbourne
Riad Wahby, Carnegie Mellon University
Joseph Bonneau, a16z crypto research/NYU/University of Melbourne

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 incurs 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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. PETS 24
Contact author(s)
faxing wang @ student unimelb edu au
cohneys @ unimelb edu au
riad @ cmu edu
jbonneau @ gmail com
2023-12-21: last of 3 revisions
2023-12-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Faxing Wang and Shaanan Cohney and Riad Wahby and Joseph Bonneau},
      title = {{NOTRY}: deniable messaging with retroactive avowal},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1926},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.