Paper 2025/204

Simpler and Stronger Models for Deniable Authentication

Abstract

Deniable Authentication is a highly desirable guarantee for secure messaging: it allows Alice to authentically send a message $m$ to a designated receiver Bob in a *Plausibly Deniable* manner. Concretely, while Bob is guaranteed Alice sent $m$, he cannot convince a judge Judy that Alice really sent this message---even if he gives Judy his secret keys. This is because Judy knows Bob *can* make things up. This paper models the security of Multi-Designated Verifier Signatures (MDVS) and Multi-Designated Receiver Signed Public Key Encryption (MDRS-PKE)---two (related) types of schemes that provide such guarantees---in the Constructive Cryptography (CC) framework (Maurer and Renner, ICS '11). The only work modeling dishonest parties' ability of "making things up" was by Maurer et al. (ASIACRYPT '21), who modeled the security of MDVS, also in CC. Their security model has two fundamental limitations: 1. deniability is not guaranteed when honest receivers read; 2. it relies on the CC-specific concept of specifications. We solve both problems. Regarding the latter, our model is a standard simulator-based one. Furthermore, our composable treatment allowed to identify a new property, Forgery Invalidity, without which we do not know how to prove the deniability of neither MDVS nor MDRS-PKE when honest receivers read. Finally, we prove that Chakraborty et al.'s MDVS (EUROCRYPT '23) has this property, and that Maurer et al.'s MDRS-PKE (EUROCRYPT '22) preserves it from the underlying MDVS.