© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Participation Deniability in Secure Messaging and the Signal Case Study

Robin Jadoul

Published Jan 1, 2020• 0 citations

Abstract

Secure messaging protocols have come to take a central role in modern, internet-based communication.Besides the common notions of confidentiality and authentication, many protocols also aim to provide a form of deniability.A deniable protocol enables parties to plausibly deny certain claims about their communication to a third party, the Judge.For example, participation deniability allows communicating parties to claim that any evidence of communication happening could have been fabricated by some other party.This can be especially useful when dealing for example with oppressive regimes that want to punish communication to international press.Therefore, in this thesis, we formalize one form of deniability, participation deniability, for two-party secure messaging protocols.We consider both an offline setting, in which the Judge only has access to evidence of a past conversation, and an online setting, where the Judge can directly observe and influence the conversation.In addition, the possibility for one or both parties to have their state leaked is taken into account.We investigate the relations between our varying notions of deniability and prove the impossibility of a protocol both providing full online deniability and authentication.Afterwards, we analyse the Signal protocol within this context.To circumvent the aforementioned impossibility, we introduce a relaxed version of our online model and continue to show that the Signal protocol can achieve this notion of online deniability.i

DOI: 10.3929/ethz-b-000413212

Related papers

Fully Deniable Message Authentication Protocols Preserving Confidentiality

Lein Harn, Chiou‐Yng Lee, C. Lin +1 more

Although the objective of secure communication can be achieved by using cryptographic tools, the undeniability that results from cryptographic properties may create a potential threat to the sender of the message. Unfortunately, most existing deniable protocols only provide 1-out-of-2 deniability. When both parties (the sender and the receiver) are allowed to deny generating the message, a dispute might occur between these two parties. The 1-out-of-2 deniable protocol can result in an unfair resolution of the dispute. Therefore, we propose a new model of deniability, called 1-out-of-∞ deniability, that can provide full deniability. The 1-out-of-∞ deniability protocol allows the originator of the message to deny that he or she generated the message, since there are an infinite number of possible message generators; at the same time, all transmitted messages can be protected and authenticated between the sender and the intended receiver. Our design can be implemented by using any public-key cryptography technique. We also analyze the correctness of the proposed protocols based on logical rules, and two practical examples are given to illustrate our design.

The Computer Journal•Aug 23, 2011•8 citations

Deniable Authentication on the Internet.

Shaoquan Jiang

Abstract. Deniable authentication is a technique that allows one party to send messages to another while the latter can not prove to a third party the fact of communication. In this paper, we first formalize a natural notion of deniable security and naturally extend the basic authenticator theorem by Bellare et al. [2] to the setting of deniable authentication. Of independent interest, this extension is achieved by defining a deniable MT-authenticator via a game. This game is essentially borrowed from the notion of universal composition [8] although we do not assume any result or background about it. Then we construct two deniable MT-authenticators: uncontrollable random oracle based and the PKI based, both of which are just 3-round protocols. The second construction assumes the receiver owns a secret key. Such a setup assumption is very popular in the real world. (Without this assumption), all the previous protocols do not have a widely satisfiable performance when applied in the Internet-like environment. Finally, as our application, we obtain key exchange protocols that is deniably secure in the real world. 1

•Jan 1, 2007•0 citations

New approaches for deniable authentication

Mario Di Raimondo, Rosario Gennaro

Deniable Authentication protocols allow a Sender to authenticate a message for a Receiver, in a way that the Receiver cannot convince a third party that such authentication (or any authentication) ever took place.We present two new approaches to the problem of deniable authentication. The novelty of our schemes is that they do not require the use of CCA-secure encryption (all previous known solutions did), thus showing a different generic approach to the problem of deniable authentication. This new approach is practically relevant as it leads to more efficient protocols and security reductions.In the process we point out a subtle definitional issue for deniability. In particular we propose the notion of forward deniability, which requires that the authentications remain deniable even if the Sender wants to later prove that she authenticated a message. We show that forward deniability is not implied by the original notion of deniability, by showing some deniable protocols which are not forward deniable. Our new proposals are forward deniable.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 7, 2005•69 citations

Cryptanalysis of a suite of deniable authentication protocols

Runze Zhu, Duncan S. Wong, C.H. Lee

A deniable authentication protocol allows a sender to transfer an authenticated message to a receiver in such a way that the receiver cannot prove to a third party about the source of the message. In 2001, Deng et al. proposed two deniable authentication protocols under the communication model defined by Aumann and Rabin in 1998. In this paper, we show that these two protocols have a common issue, which incurs vulnerability to the person-in-the-middle (PIM) attack. We also propose a modification for solving the problem.

IEEE Communications Letters•Jun 1, 2006•25 citations

On the Deniability of Some Deniable Authentication Protocols

Meng-Hui Lim, Sang-Gon Lee, Hoon Jae Lee

A deniable authentication protocol enables the protocol participants to authenticate their respective peers, while able to deny their participation after the protocol execution. This protocol can be extremely useful in some practical applications such as online negotiation and electronic voting. In 2007, Ma et al. proposed a chameleon-based deniable authenticated key agreement protocol while in 2006, Lin-Chang proposed another improved deniable authentication protocol. However, we discover that both these schemes are in fact undeniable due to some flaws in their protocol design. In this paper, we prove the opposite of their claims and discuss the undeniability of their schemes in detail.

International Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies (UBICOMM)•Sep 1, 2008•0 citations

Deniable Key Exchanges for Secure Messaging

Nik Unger, Ian Goldberg

In the wake of recent revelations of mass government surveillance, secure messaging protocols have come under renewed scrutiny. A widespread weakness of existing solutions is the lack of strong deniability properties that allow users to plausibly deny sending messages or participating in conversations if the security of their communications is later compromised. Deniable authenticated key exchanges (DAKEs), the cryptographic protocols responsible for providing deniability in secure messaging applications, cannot currently provide all desirable properties simultaneously. We introduce two new DAKEs with provable security and deniability properties in the Generalized Universal Composability framework. Our primary contribution is the introduction of Spawn, the first non-interactive DAKE that offers forward secrecy and achieves deniability against both offline and online judges; Spawn can be used to improve the deniability properties of the popular TextSecure secure messaging application. We also introduce an interactive dual-receiver cryptosystem that can improve the performance of the only existing interactive DAKE with competitive security properties. To encourage adoption, we implement and evaluate the performance of our schemes while relying solely on standard-model assumptions.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 6, 2015•44 citations

Secure messaging protocols have come to take a central role in modern, internet-based communication.Besides the common notions of confidentiality and authentication, many protocols also aim to provide a form of deniability.A deniable protocol enables parties to plausibly deny certain claims about their communication to a third party, the Judge.For example, participation deniability allows communicating parties to claim that any evidence of communication happening could have been fabricated by some other party.This can be especially useful when dealing for example with oppressive regimes that want to punish communication to international press.Therefore, in this thesis, we formalize one form of deniability, participation deniability, for two-party secure messaging protocols.We consider both an offline setting, in which the Judge only has access to evidence of a past conversation, and an online setting, where the Judge can directly observe and influence the conversation.In addition, the possibility for one or both parties to have their state leaked is taken into account.We investigate the relations between our varying notions of deniability and prove the impossibility of a protocol both providing full online deniability and authentication.Afterwards, we analyse the Signal protocol within this context.To circumvent the aforementioned impossibility, we introduce a relaxed version of our online model and continue to show that the Signal protocol can achieve this notion of online deniability.i

Although the objective of secure communication can be achieved by using cryptographic tools, the undeniability that results from cryptographic properties may create a potential threat to the sender of the message. Unfortunately, most existing deniable protocols only provide 1-out-of-2 deniability. When both parties (the sender and the receiver) are allowed to deny generating the message, a dispute might occur between these two parties. The 1-out-of-2 deniable protocol can result in an unfair resolution of the dispute. Therefore, we propose a new model of deniability, called 1-out-of-∞ deniability, that can provide full deniability. The 1-out-of-∞ deniability protocol allows the originator of the message to deny that he or she generated the message, since there are an infinite number of possible message generators; at the same time, all transmitted messages can be protected and authenticated between the sender and the intended receiver. Our design can be implemented by using any public-key cryptography technique. We also analyze the correctness of the proposed protocols based on logical rules, and two practical examples are given to illustrate our design.

Abstract. Deniable authentication is a technique that allows one party to send messages to another while the latter can not prove to a third party the fact of communication. In this paper, we first formalize a natural notion of deniable security and naturally extend the basic authenticator theorem by Bellare et al. [2] to the setting of deniable authentication. Of independent interest, this extension is achieved by defining a deniable MT-authenticator via a game. This game is essentially borrowed from the notion of universal composition [8] although we do not assume any result or background about it. Then we construct two deniable MT-authenticators: uncontrollable random oracle based and the PKI based, both of which are just 3-round protocols. The second construction assumes the receiver owns a secret key. Such a setup assumption is very popular in the real world. (Without this assumption), all the previous protocols do not have a widely satisfiable performance when applied in the Internet-like environment. Finally, as our application, we obtain key exchange protocols that is deniably secure in the real world. 1

Deniable Authentication protocols allow a Sender to authenticate a message for a Receiver, in a way that the Receiver cannot convince a third party that such authentication (or any authentication) ever took place.We present two new approaches to the problem of deniable authentication. The novelty of our schemes is that they do not require the use of CCA-secure encryption (all previous known solutions did), thus showing a different generic approach to the problem of deniable authentication. This new approach is practically relevant as it leads to more efficient protocols and security reductions.In the process we point out a subtle definitional issue for deniability. In particular we propose the notion of forward deniability, which requires that the authentications remain deniable even if the Sender wants to later prove that she authenticated a message. We show that forward deniability is not implied by the original notion of deniability, by showing some deniable protocols which are not forward deniable. Our new proposals are forward deniable.

A deniable authentication protocol allows a sender to transfer an authenticated message to a receiver in such a way that the receiver cannot prove to a third party about the source of the message. In 2001, Deng et al. proposed two deniable authentication protocols under the communication model defined by Aumann and Rabin in 1998. In this paper, we show that these two protocols have a common issue, which incurs vulnerability to the person-in-the-middle (PIM) attack. We also propose a modification for solving the problem.

A deniable authentication protocol enables the protocol participants to authenticate their respective peers, while able to deny their participation after the protocol execution. This protocol can be extremely useful in some practical applications such as online negotiation and electronic voting. In 2007, Ma et al. proposed a chameleon-based deniable authenticated key agreement protocol while in 2006, Lin-Chang proposed another improved deniable authentication protocol. However, we discover that both these schemes are in fact undeniable due to some flaws in their protocol design. In this paper, we prove the opposite of their claims and discuss the undeniability of their schemes in detail.

In the wake of recent revelations of mass government surveillance, secure messaging protocols have come under renewed scrutiny. A widespread weakness of existing solutions is the lack of strong deniability properties that allow users to plausibly deny sending messages or participating in conversations if the security of their communications is later compromised. Deniable authenticated key exchanges (DAKEs), the cryptographic protocols responsible for providing deniability in secure messaging applications, cannot currently provide all desirable properties simultaneously. We introduce two new DAKEs with provable security and deniability properties in the Generalized Universal Composability framework. Our primary contribution is the introduction of Spawn, the first non-interactive DAKE that offers forward secrecy and achieves deniability against both offline and online judges; Spawn can be used to improve the deniability properties of the popular TextSecure secure messaging application. We also introduce an interactive dual-receiver cryptosystem that can improve the performance of the only existing interactive DAKE with competitive security properties. To encourage adoption, we implement and evaluate the performance of our schemes while relying solely on standard-model assumptions.