Paper 2025/204

On the Composable Security of MDVS and MDRS-PKE Constructions

Abstract

Off-The-Record (OTR) messaging applications are designed to provide so-called Deniable Authentication guarantees. These allow a sender Alice to designate a receiver Bob and sign him a message m that only he can validate. While Bob is guaranteed Alice signed m, he cannot convince non-designated Judy that Alice signed m, even if he gives Judy his secret keys. This is because, as Judy knows, Bob could have forged that signature. In recent work, Liu-Zhang, Portmann and Rito construct the first fully Off-The-Record group messaging application (ePrint 2024/1593). Central to their construction are new idealized communication channels that provide rather strong Deniable Authentication guarantees. While these channels are introduced to capture the guarantees provided by Multi-Designated Verifier Signatures (MDVS) and Multi-Designated Receiver Signed Public Key Encryption (MDRS-PKE) schemes, no scheme is proven to construct them. More, the only composable treatment of MDVS schemes does not guarantee deniability for messages that are read by honest parties (Maurer, Portmann and Rito, ASIACRYPT ’21). In contrast, however, the channels assumed for the construction of the OTR messenger provide this guarantee, meaning their OTR messenger has no known provably secure instantiations. We close this gap by providing a new (generic) composable treatment of MDVS and MDRS-PKE schemes. Interestingly, our treatment allowed us to identify a new property, Forgery Invalidity, without which we do not know how to prove the deniability of neither MDVS nor MDRS-PKE schemes when honest receivers read. We show that any MDVS and MDRS-PKE scheme providing this guarantee (plus other known ones) constructs the idealized channel semantics that are assumed by Liu-Zhang, Portmann and Rito’s OTR messenger construction. Then, 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. Together, our results imply that Liu-Zhang, Portmann and Rito’s OTR messenger can be securely instantiated from Chakraborty et al.’s MDVS, or from Maurer et al.’s MDRS-PKE.