Paper 2023/213

Deniable Authentication when Signing Keys Leak

Suvradip Chakraborty, Visa Research
Dennis Hofheinz, ETH Zurich
Ueli Maurer, ETH Zurich
Guilherme Rito, ETH Zurich

Deniable Authentication is a highly desirable property for secure messaging protocols: it allows a sender Alice to authentically transmit messages to a designated receiver Bob in such a way that only Bob gets convinced that Alice indeed sent these messages. In particular, it guarantees that even if Bob tries to convince a (non-designated) party Judy that Alice sent some message, and even if Bob gives Judy his own secret key, Judy will not be convinced: as far as Judy knows, Bob could be making it all up! In this paper we study Deniable Authentication in the setting where Judy can additionally obtain Alice's secret key. Informally, we want that knowledge of Alice's secret key does not help Judy in learning whether Alice sent any messages, even if Bob does not have Alice's secret key and even if Bob cooperates with Judy by giving her his own secret key. This stronger flavor of Deniable Authentication was not considered before and is particularly relevant for Off-The-Record Group Messaging as it gives users stronger deniability guarantees. Our main contribution is a scalable ``MDRS-PKE'' (Multi-Designated Receiver Signed Public Key Encryption) scheme---a technical formalization of Deniable Authentication that is particularly useful for secure messaging for its confidentiality guarantees---that provides this stronger deniability guarantee. At its core lie new MDVS (Multi-Designated Verifier Signature) and PKEBC (Public Key Encryption for Broadcast) scheme constructions: our MDVS is not only secure with respect to the new deniability notions, but it is also the first to be tightly secure under standard assumptions; our PKEBC---which is also of independent interest---is the first with ciphertext sizes and encryption and decryption times that grow only linearly in the number of receivers. This is a significant improvement upon the construction given by Maurer et al. (EUROCRYPT '22), where ciphertext sizes and encryption and decryption times are quadratic in the number of receivers.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
Deniable AuthenticationOff-The-RecordMDRS-PKEMDVSPKEBC
Contact author(s)
suvradip1111 @ gmail com
hofheinz @ inf ethz ch
maurer @ inf ethz ch
gteixeir @ inf ethz ch
2023-02-20: approved
2023-02-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Suvradip Chakraborty and Dennis Hofheinz and Ueli Maurer and Guilherme Rito},
      title = {Deniable Authentication when Signing Keys Leak},
      howpublished = {Cryptology ePrint Archive, Paper 2023/213},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.