---
title: TADA Part 2
tags: [cryptography, protocols]

---
# TADA 🎉 Part 2: Into the TADA-Verse

We followed the construction of **TADA**, **time-assured deniable authentication**, in [Part 1](https://hackmd.io/@topo/S1do9kwnke) as a protocol for plausibly deniable proofs.

:::warning
:warning: This post is not rigorous. I had a handful of ideas for how TADA could be used and eventually they started taking the ~~length~~ shape of a longer-form blogpost.
:::

To me, one of the coolest parts about TADA is how it invokes **ephemeral communication channels** that mirror the space in which real-life interactions are often naturally embedded. I think these ephemeral communication channels are the key to bringing online a lot of applications falling under the umbrella of "situations that require plausible deniability", and maybe even beyond that when used in especially creative ways.

So here's a few (rough) ideas! Feedback is very much welcome :)

## Whistleblowing

The classic digital use-case for deniable authentication.

Authenticate a message containing to sensitive information to a reporter knowing that the proof of your identity will disappear over time. This allows for journalists to partake in real-time conversations and protect the identity of their interviewee from authorities.

We basically use the same protocol as [Encryption-TADA](https://hackmd.io/b9e47uvCQ7u8psDqM05toA?view#Encryption-TADA), but instead of encrypting to the verifier randomness directly we encrypt to the concatenation of a message with the randomness, $m\circ r$. This scheme has also been proposed by [Dwork and Naor](https://www.wisdom.weizmann.ac.il/~naor/PAPERS/zap.pdf).

However, Encryption-TADA begins with the *verifier sending a message $m$ to the prover,* which only allows the prover to **authenticate to messages set by the verifier**. To get around this, we'll just have the prover post messages to some kind of anonymous message board only the prover and verifier are permissioned to post in. After every new message, the verifier will simply run the following protocol.

Even if this message board is public, this protocol is secure. Since the verifier knows the opening to the committed value, the verifier could have easily generated every message along with an accepting response to the protocol, making all authentication proofs appear deniable from the outside.

#### Protocol Outline

1. $P$ and $V$ initialize an anonymous message board instance.
2. To send a message, $P$ posts $m$ to the message board.
4. Upon seeing a new message, $V$ uses [timed commitment scheme](https://hackmd.io/b9e47uvCQ7u8psDqM05toA?view#An-Introduction-to-Timed-Commitments) $\zeta(T, t, \epsilon)$ to generate the commitment $\left<c, \pi_{0} \right> \leftarrow \mathsf{Commit}(N, T, r)$ to some random value $r\leftarrow \mathbb{Z}_N$ for security parameter $N$.
5. $V$ additionally generates an encryption $\mathbf{e} := \mathsf{Enc}_P(m\circ r)$ of $r$ to some public key $\mathsf{pk_P}$.
6. $V$ generates a zero-knowledge proof $\pi$ that the opening of $c'$ is equal to *the suffix of the value encrypted by* $\mathbf{e}$.
8. $V$ sends to the prover $P$ the tuple $\left<c', \pi_0, \mathbf{e}, \pi\right>$.
9. If $m$ was generated by $V$, $V$ immediately sends $r$ in the clear to $P$.
10. $P$ checks that $\pi$ is valid and decrypts $\mathbf{e}$ to $\mathsf{Dec}(\mathbf{e}) = m\circ r'$.
11. If $m$ is a message that $P$ wishes to authenticate, $P$ sends $r'$ in the clear before time $t$ has passed for $V$.
12. $V$ verifies that $r' == r$.

Since this protocol is run for each new message, step 7 is necessary to prevent the prover from authenticating to any messages that aren't theirs. There's nothing really stopping the verifier from doing this after each step, but there's also no incentive to incapacitate the prover from authenticating to anything if this channel was opened in the first place.

## Deniable Ghosting

Deniable authentication can also be fun!

Match with someone on a dating app-- however, if one person hasn't sent a message after some time, *there's no trace that you've ever matched at all*. This seems kind of outrageous, but it forces people to be more engaged in their conversations and move them offline quicker! There's also no shortage of situations in dating where people are met with persistence that feels unsafe and don't really know how to respond or deem worthy of reporting.

We can actually make this protocol fully with Encryption-TADA! We'll assume that our dating app has the following:
- A centralized server.
- Some number of pre-existing chatroom entities with preassigned ids.

We will not roll out the specifics of how these chatrooms are created, assigned or maintained in this blog. We suggest pre-existing chatroom instances for this application to guard against matches being leaked by chatroom creation events.

Additionally, we'll involve the following public parameters:
- Some security parameter $N$.
- Time values $t$ and $T$ to be used in a timed commitment scheme $\zeta(T, t, \epsilon).$

Let's say Alice and Bob (A and B) formed a match. In this system, the verifier will be a server $V$ who will only maintain a chat interface between Alice and Bob **if they continue to jointly provide valid TADA verifications.** Matching is equivalent to A making the claim "B and I *both* know the secret key corresponding to this shared public key, and we can send and receive messages from this chatroom" to the server, and vice versa for B.


#### Protocol Outline
1. When A and B match, they blind their secret keys and share them with each other to create the new key-pair $(\mathsf{pk}_{AB}, \mathsf{sk}_{AB})$.
3. The server randomly assigns A and B to an existing chatroom instance.
4. $V$ generates two randomness values $r_A \leftarrow \mathbb{Z}_N$ and $r_B \leftarrow \mathbb{Z}_N$.
5. $V$ uses $\zeta(T, t, \epsilon)$ to generate $\left<c_A, \pi_{0}^A \right> \leftarrow \mathsf{Commit}(N, T, r_A)$ and $\left<c_B, \pi_{0}^B \right> \leftarrow \mathsf{Commit}(N, T, r_B)$.
6. $V$ encrypts $\mathbf{e_A} = \mathsf{Enc}_{AB}(r_A)$ and $\mathbf{e_B} = \mathsf{Enc}_{AB}(r_B)$ to the shared public key.
7. $V$ generates $\pi_A, \pi_B$, where $\pi_{-}$ is a zero-knowledge proof that the opening to $c_{-}$ and plaintext of $\mathbf{e}_{-}$ are equal.
8. $V$ simultaneously sends to $\left<c_A, \pi_0^A, \mathbf{e_A}, \pi_A \right>$ to **only A** and $\left<c_B, \mathbf{e_B}, \pi_0^B, \pi_B\right>$ to **only B**.
9. After a message from $V$ is received, each user's client automatically verifies $\pi_0^-$ and $\pi_-$.
10. When A sends a message $m$ to the chatroom, their client automatically performs the following operations:
- Broadcast $\mathsf{Enc_{AB}}(m)$ to the server with the chatroom id
- Decrypt $\mathbf{e_A}$, and
- Send the $r'_A = \mathsf{Dec}(\mathbf{e_A})$ to $V$ in the clear
12. $V$ broadcasts $\mathsf{Enc_{AB}}(m)$ to the chatroom with the specified id.
13. Before time $t$ has elapsed, $V$ must receive **BOTH** $r'_A = r_A$ from A and $r'_B = r_B$ from B. Otherwise, $V$ ejects A and B from the chatroom.
14. If both messages are received, $V$ immediately repeats steps 3-11.

Note that although the central ephemeral communication channel (the chatroom) created is between A and B, it's sustained by ephemeral communication channels (protocol interactions) bewteen the users and *the server*. This not only leverages the existing computational power of the server to maintain these ephemeral chatrooms, but also ensures that the base functionalities of a dating app, such as uploading profiles, matching algorithms, etc, remain efficient. In that lens, this protocol is also a boilerplate answer to the question of how to build efficient ephemeral communication channels on top of centralized applications.

*How do you prevent against visual recordings?* We can require the app to be screenshot resistant, we can't really prevent against someone who records with another person's phone, but I think this is maybe okay. The purpose of the deniability here is more about preventing someone from continually contacting you.

## Plausibly Deniable Digital ID Attestation
The ongoing design of digital identity ecosystems such as the [EU Digital Identity wallet](https://eu-digital-identity-wallet.github.io/eudi-doc-architecture-and-reference-framework/latest/) represent a large-scale effort to reshape the information landscape to give individuals more control over their data. They're also an especially exciting use case for deniable authentication protocols as a tool for ensuring that attestation proofs are untraceable.

Digital identity ecosystems are built on the principle of **self-sovereign identity,** where individuals have full custody of the credentials issued to them. This means that a verifier can *only learn about a prover's credentials from interactions with the prover herself.* Deniable authentication protocols should not only uphold this principle, but also be structured to be compatible with the other existing design specs of a self-sovereign identity ecosystem.

As of April 2025, there is no proposed mechanism for ensuring plausibly deniable interactions in the current edition of the [EUDI Wallet Architecture and Reference Framework](https://eu-digital-identity-wallet.github.io/eudi-doc-architecture-and-reference-framework/1.1.0/arf/#532-attestation-releasing). We propose a framework based on [Vanilla-TADA](https://hackmd.io/b9e47uvCQ7u8psDqM05toA?view#Vanilla-TADA) for designing **self-sovereign deniable authentication** protocols.

### A Brief Architecture Overview of EUDI Wallet Interactions

To my understanding, the current proposed EUDI Wallet architecture looks something like this: every user has an authenticated *wallet unit* (through WebAuthen, FaceID etc.) which holds a number of credentials, along with an information object about the wallet itself [(A.2.3.9 Topic 9)](https://eu-digital-identity-wallet.github.io/eudi-doc-architecture-and-reference-framework/latest/annexes/annex-2/annex-2-high-level-requirements/). The wallet unit also contains a cryptographic key manager that links the public key of each credential has to the secret key of this wallet information object.


When you want to interact with a *relying party (RP)* like a liquor store or a customs office, you present them with a proof that the wallet linked to your userame (psuedonym) has the credentials they require.

Each RP publishes a [presentation definition](https://identity.foundation/presentation-exchange/#presentation-definition) $C(x, \cdot)$ that articulates the types credentials it requires from a user wallet.

#### Trust Relationships Outlined by the EUDI

[Section 5.3.2.1](https://eu-digital-identity-wallet.github.io/eudi-doc-architecture-and-reference-framework/1.1.0/arf/#5231-required-trust-relationships) of the EUDI architecture and reference framework requires the following trust relationships to exist between a RP and a user who wishes to interact with it.

> :::spoiler When a Relying Party (RP) requests a User to release some attributes from his/her EUDI Wallet Instance, the following trust relationships must exist:
> 1. The RP must be able to trust the Issuer.
> 2. The RP must be able to trust that the attestation released by the EUDI Wallet Instance is authentic, meaning that it originated from a trusted Issuer and has not been changed.
> 3. The RP must be able to trust that the Issuer issued this attestation to the EUDI Wallet Instance that provided it to the RP. In other words, the attestation was not copied and replayed. This is generally called device binding.
> 4. The RP must be able to trust User binding. This means that the person presenting the attestation is the same one as the User, i.e., the person to whom the attributes in the attestation apply.
> 5. The User must be able to trust the Relying Party, meaning that the User is sure about the RP’s identity.
> 6. In some use cases the User must be able to trust that the RP does not request more data than it reasonably needs for the use case.

These relationships give insight into the other cryptographic tools we can assume will be available in the ecosystem. Specifically, we can infer the existence of the following mechanisms:
- $\mathsf{RPAuthen}$, through which the User verifies the RP's identity.
- $\mathsf{VerifyWalletBind}$, which verifies that a credential is bound to the EUDI Wallet Instance.

$\mathsf{VerifyWalletBind}$ consists of a wallet instance producing a signature to some metadata specific to the interaction (like a nonce) with the private key of the credential required by the RP presentation definition. Data types like [SD-JWT] can implement $\mathsf{VerifyWalletBind}$ through including an attestation public key in the JWT, and sending a zero-knowledge proof of the existence of this term to be verified by the RP.

We can wrap $\mathsf{VerifyWalletBind}$ in a zero-knowledge proof to get verifiable correctness of the signature while avoiding the disclosure of the public key of the attestation credential.

### Protocol outline

We assume that user wants to authenticate to an RP with presentation definition $C(\cdot, x)$. For programmability, we does not make any assumptions over the data type of the user credential!

Our final protocol follows pretty closely to Vanilla-TADA, with a few notable exceptions.

The original TADA model assumes that the verifier already knows the public keys of all provers it will interact with. For a new prover to enter this protocol, they'll simply need to start the interaction by sending their public key to the verifier in $\mathsf{RPAuthen}$.

1. $P$ runs $\mathsf{RPAuthen}$ with $V$, sharing its psuedononymous public key $\mathsf{pk}_P$ if and only if it succeeds.
2. After $\mathsf{RPAuthen}$ succeeds, $V$ $V$ uses timed commitment scheme $\zeta(T, t, \epsilon)$ to generate the commitment $\left<c, \pi_{0} \right> \leftarrow \mathsf{Commit}(N, T, r)$ to some random value $r\leftarrow \mathbb{Z}_N$ for security parameter $N$.
8. $V$ sends to prover $P$ the message $\left<\zeta (r), \mathbf{e}, s\right>$, where $s$ is the nonce to be used in $\mathsf{VerifyWalletBind}$.
11. Before $t$ has elapsed for the verifier since their previous message, $P$ sends to the prover the following zero-knowledge proof $\pi$:
- $\mathsf{VerifyWalletBind}(s)$ passes.
- $P$ has some $(x, w)$ such that $C(x, w)$ accepts, OR
- $P$ knows the value $r$ of the opening to $\zeta (r)$.
12. $V$ accepts if $\pi$ is received in a timely manner and accepts.

Separately from $\mathsf{PRAuthen}$, this protocol runs in 2 rounds of communication. If the RP receives the wallet response before time $t$, then they will know that the user has provided a legitimate proof of having the necessary credentials. Receiving a valid $\pi$ after expiry will not permit the RP to accept the attestation, and the RP learns nothing about the user.

**How do we make sure no one authenticates with someone else's proof?** We can require in the circuit that this proof is somehow tied to the prover's public key. Additionally, we can limit the verifier to accepting at most one proof for each public key per challenge sent, by using nullifiers for whenever a verifier recieves a fresh proof claiming to be from the same public key.

### BBS+ Deniable Authentication


BBS+ is a signature-based selective disclosure scheme built to uphold **verifier unlinkability**, which prevents verifiers that have interacted with the same prover from colluding to learn the prover's activity. BBS is a popular candidate for introducing plausible deniable to attestation schemes in the current design of digital identity ecosystems. The details of the protocol are out of the scope of this blogpost, but comparisons between BBS and TADA demonstrate the tradeoffs between *different interpretations of plausible deniability*.

This direction seems especially aligned with the proposed guidelines of how wallet units can be expected to securely organize pseudonyms generated by the user. In many networks, however, it is unrealistic to assume that users will want to comply with the overhead of creating a new psuedonym to use with every unique individual.