Paper 2023/213

Deniable Authentication when Signing Keys Leak

Abstract

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.

Note: As noted by Maurer et al. in (ePrint 2022/256), it is not clear how to prove the off-the-record security of the MDRS-PKE construction given in (Eurocrypt '22). Fortunately, also in (ePrint 2022/256), Maurer et al. show how to fix their construction so all security proofs, including off-the-record, go through. In an earlier version of this paper we considered the original MDRS-PKE construction given by Maurer el al. in (Eurocrypt '22), and claimed that the same security proofs with minor adaptations would work for the setting considered in this paper. While for the most part this is still the case, unfortunately for (IND+IK)-CCA-2 security the arguments given in (ePrint 2022/256) do not seem to apply for the setting we consider in this paper (where the adversary is given access to the secret key of honest senders). To fix this issue, in this new (full) version we introduce a new security notion for MDVS schemes---Message-Bound Validity---with which we can prove the security of the (modified) MDRS-PKE construction from (ePrint 2022/256) in the new setting considered in this paper. We also prove that our MDVS construction satisfies this new Message-Bound Validity notion. While these are the main changes in this new full-version, we made other smaller fixes.