Let’s start with Zero Knowledge Proof — arguably the one of the most important discovery of modern cryptography and computer science. Given the fact that cryptographers are not great at naming things, it is no surprise that ZKP is made up of three most philosophical words out there, which is fitting since the concept itself is full of intricacies and subtleties. Worse, the field is moving so fast in both theoretical and implementation directions, that it becomes all but impossible to catch up (I speak this only for myself, of course).

Zero Knowledge Proofs

The whole field is nicely captured in the community-driven documentation [1]. I am summarizing the main points below.

A ZKP is a proof system that is zero-knowledge. A proof system has a Prover and a Verifier, and the former wants to convince the later that a statement is true. There are three security properties.

1. Completeness: basically, if the statement is true, the Verifier is convinced.

2. Soundness: if the statement is not true, the Verifier is not convinced.

3. Zero knowledge: the Verifier learns nothing more during the interaction with the Prover, except for the fact that the statement is true.

Now, if you were like me and went to Wikipedia for some initial explanation of ZKP, you may remember the cave example in which the Prover tries to convince the Verifier that he knows how to unlock a door inside the cave. One thing that really stays with me about that example is that it explains another property: an observer watching the video of the interaction is not convinced that the Prover knows the secret (to unlock the door). Until know, I associated this example with the zero knowledge property: if some third party gains no knowledge from observing an interaction, then the protocol is zero-knowledge. Of course, zero knowledge is far more than that. At the least, my association cannot explain Non-Interactive Zero Knowledge (NIZK) systems, ones being dragged to the spotlight by the usage in blockchains.

I will now try to unravel my initial naive understanding of ZKP.

Proof statement vs. proof of knowledge The nature of the statement being proof is important. If it concerns fact, such that “this number can be factored”, is easy. Most ZKP systems, however, concerns knowledge. What is knowledge? We cannot model philosophical concepts, only mathematical ones. So knowledge here is simple a secret. A statement of the form “I know such that ..." where is not obvious, represents some knowledge. One example is where the secret is the discrete log of an element in a prime order group. A zero knowledge proof for a statement of that form is a **zero knowledge proof of knowledge**. We will assume this for the rest of the article whenever ZKP is mentioned.

Note that the zero knowledge property implies that the Verifier cannot learn the secret during interaction with the Prover. This directly extends to the scenario when the Verifier show its transcripts to a third party: that party cannot learn the secret either. The zero knowledge property implies non-transferability, when it comes to the secret itself. So far, so good.

Interactive vs. non-interactive The interaction between Prover and Verifier is undesirable for performance, since it assumes both parties to be online and responsive. Among the first effort in reducing, if not removing, the interaction, Fiat-Shamir proposed a method that turns any 3-phase ZKP protocol, called a Sigma protocol, into non-interactive version.

• Sigma protocol: Prover sends a commitment, Verifier replies with a challenge, and Prover sends the response.

• FS NIZK: Prover uses a hash of the commitment as the challenge, assuming the hash function is model as a random oracle.

At first, I was flummoxed by this. Something seems shaky, since the Prover can choose the commitment, he knows the challenge in advance, as oppose to the challenge being out of his control. I was worried that the Prover can convince the Verifier that he knows something while in fact he doesn’t — precisely the definition of soundness. However, due to cryptographic hardness assumption, the Prover can only fake the valid response to a challenge if he knows the secret. Sure, he can try his luck with many different challenges, but he is bound computationally and therefore cannot succeed. Furthermore, he cannot even choose the challenges deliberately, since he can only control their pre-images and cannot control the output of the random oracle.

Having understood soundness, I now untangle the zero knowledge property for NZIK. All the papers on ZNIK provide proofs for this property, which is based on a simulator generating the same transcript as a Prover, do not discuss what it means for transferability. Similar to the interactive case, zero knowledge means the secret is safe. However, the fact that the interaction is completely public means any one can be the verifier. Indeed, FS NIZK proof doesn’t have any information about the Verifier. It being publicly verifiable means that something is definitely transferable. If not the secret itself, then what? The answer here is: the Prover knows the secret. Yes, the Verifier can take the proof, shows it to a third party, and convinces that party the Prover knows the secret. Not that the Verifier knows, but the Prover knows.

Wow, wow,…, take a step back here. Then what is NOT transferred in the interactive case? The secret, sure. But also the fact that the Prover knows the secret. Again, in the interactive ZKP, a third party seeing only the interaction cannot be convinced that the Prover knows the secret. Being convinced here means the proof unsound: the verification computation accepts the proof only when the Prover knows the secret. It squares nicely with the cave example from Wikipedia: the observer seeing the interaction on video is not cryptographically convinced that the Prover know, since he may have faked the whole thing with the Verifier.

Transferability is not the same as zero knowledge which is about not leaking the secret. Instead, it is about showing the proof’s soundness to a third party. In other words, a proof is transferable if the Verifier can use it to cryptographically convince the third party that the Prover knows a secret.

It is easy to see that moving from interactive to non-interactive implies transferability, or it loses non-transferability. Going back to the cave example, the observer given a NIZK proof is now convinced that the Prover knows the secret to unlock the door.

Attempting a Definition of Transferability

Let’s try to somewhat formally define transferability. The protocol now consists of a Prover, a Verifier, and an Observer. The syntax is roughly as follows:

• Setup(): generate some public parameters
• Prove(s): generate a proof for statement s
• Verify(p): accept or reject the proof

The Verifier has some private states that can be used to generate the proof. The Observer does not have access to such states. The soundness of the proof system means that Verifier.Verify(p) accepts the proof only when s is true. If Observer.Verify(p) accepts only when s is true, then the proof is transferable, else it is non-transferable.

Deniability

One cool side consequence of non-transferability is that to a third party, the Prover can even deny that the interaction is real. The third party is not the Verifier, who is already convinced of the Prover’s knowledge. In other words, the Verifier takes the transcript and shows to the third party, the Prover then has plausible deniability because the Verifier could have faked the whole thing. Faking the transcript is directly implied by the zero property.

Is Non-interactive always transferable?

Without considering the semantics of the statement being proof, NIZK itself is transferable. However, we can craft the statement in a way that makes the proof non-transferable. In particular, consider the following statement:

I know the secret X, OR I know the private key of the Verifier

Now consider a NIZK proof for this statement. Given to the Verifier, it is sound since we assume only the Verifier knows its own secret key. Given to the Observer, however, he is only convinced that the statement is true, which can happen in two ways: Prover knows the secret, or Prover knows the private key. The latter can happen when Prover and Verifier collude when they don’t know X.

Other combination of deniability/non-transferability and interactiviy

[1] discuss various combinations of interactivity (interactive vs. NIZK) and transferability. Essentially, interactive proofs are not transferable, non-interactive ones are. However, transferability also depends on the semantics of the statement being proved, as the example above illustrate. Therefore, sometimes you can have interactive and transferable proofs, as well as non-interactive and non-transferable ones.

Deniability

What all of the above have to do with deniability (beside the fact that I mentioned it as a consequence of non-transferability). Deniability is the ability to convince others (cryptographically, in the ideal case) that you didn’t do something. The approach is to show a proof that other people could have done that thing too.

Deniability vs. Authentication At first glance, deniability seems in conflict with authentication. In the former, I can deny that I am the author of some message, while in the latter, I must convince someone that the message is from me. This tension is resolved we recall the above discussion about interactive proof and transferability. In particular, we can get both authentication with the Verifier, and deniability with any third party at the same time. The idea is that during interaction, the Verifier can be convinced about who the Prover is and what he says, but thereafter, the Prover can deny the content of the interaction. There is a session in which authentication holds, and outside of that session we can provide deniability.

Another clever way to reconcile these two notions is to release the key so that anyone can forge the message. It works in two steps:

1. Use public key to authenticate a session.
2. After the session ends, rotate to a new key, and release the old one.

Once the key is released, it is not possible for an attacker to prove the authenticity of the session’s content. Because anyone could have generated such content, I have deniability. The flip side of this clever trick is that there is a window of vulnerability before the key is released, within which there is no deniability.

Examples

I will talk about several examples in the context of personal communication, and refer you to read [4] which contains a lot more insights.

Example 1 - Secure messaging.

The way that we communicate online is vastly different to the way our social conversions take place offline. When we talk to our friend, we expect not only privacy, that the conversation is not overhead by someone else, but also deniability. The latter means the friend cannot convince another friend about the content of your conversion. In other words, you can argue that the friend has fabricated the content, and you did not say certain things. This is plausible deniability, and most of us understand that.

To protect privacy, most messaging apps will encrypt the message content. There are two ways to encrypt things: using pubic key crypto, or private key crypto. The latter not only gives you more performance, because symmetric key operations are fast, but also deniability. It is because two parties share the same key, thus the encrypted text can be generated by either one of them. Off-the-Record (OTR) protocol, which later turns into Signal, provides this property, and even a stronger one. The this enhanced deniability works as follows:

• OTR uses stream cipher (AES in counter mode). This cipher is malleable, in the sense that if you flip one bit in the ciphertext, the corresponding bit in the plaintext is flipped. Therefore, if an attacker knows the plaintext and the corresponding ciphertext, even without the key he can modify the ciphertext so that it is decrypted to something completely different.

• Given this malleable encryption, one of the party will then release the MAC key. By doing this, an attacker can generate a valid tag for any ciphertexts of his choice. In particular, he can choose a recorded messaged, change it to correspond to a different plaintext, then encrypt.

The second step, i.e. releasing the MAC key, makes it impossible to attribute a signed message to anyone, including any of the two communicating parties, since anyone could have generated it. This is as opposed to not releasing the key where one can at least attribute the message to one of the two parties.

Example 2 - Email.

Unlike messaging systems such as Whatsapp or Signal, the traditional email systems are asynchronous. Others have also refer to the email model as store and forward. The main property of this model is that users are not expected to be online or responsive. As one of the few remaining pioneer use cases of the Internet, emails have seen many security extension.

• PGP: supposed to provide end-to-end security for email messages, it never takes off. Not only is it hard to use and deploy, it lacks other fundamental properties for communication security, namely perfect forward security. In a forward secure system, compromising an encryption key at time \(t\) does not allow the attacker to decrypt past encrypted content at time before \(t\).

• DKIM/DMARC: proposed as an email authentication mechanism, it prevent emails from being spoofed. Basically, the sender domain public its signing keys to a public bulletin board (e.g., DNS). The sending mail server signs the message and attaches the signature to the email. At the receiver side, the mail server checks the signature before accepting the email.

PGP is basically a lost cause, so let’s focus on DKIM/DMARC. Matthew Green wrote this brilliant blog post about the problem with DKIM. It is not that DKIM is broken, but that it has an undecided side effect. The DKIM signature is publicly verifiable, and is non-deniable. While signature helps authenticate the sender, thereby preventing spoofing, non-deniability means that an attacker stealing the email dumps can convince a third party that the stolen emails are authentic. If Alice sent and email to Bob, and Bob’s mail server later got hacked, the stolen email dump contains Alice’s emails and the corresponding signatures which are undeniable evidence that the emails originated from Alice’s domain.

This issue with DKIM is an instance of the authenticity vs. deniability tension we discussed earlier. In a recent paper [3], Green and his co-authors, propose several ways to achieve both properties. One of the idea is for the sender’s mail server to periodically publish its DKIM signing keys on a bulletin board. One interesting protocol can even achieve the balance against real-time attacker that takes total control of the mail server. For deniability against such a powerful attacker, the idea is to make the email verification interactive. The authors even claim that interactivity is a necessary condition when considering real-time attacker. I couldn’t really follow the paper’s arguments behind that claim, but I can intuitively relate it to ZKP (recall earlier how interactive proof gives you both authenticity and non-transferability). For smash-and-grab attacker, verification can still be done non-interactively while guaranteeing deniability via releasing the key.

Conclusion

There are tenable connection between many cryptographic concepts. It may take a cryptographer a few theorems to recognize certain connections, but for ones like me it is more interesting when you see it from the applications. I started this article from reading Green’s blog post, then reading his paper, then finding about interactive proof system, and landing at zero knowledge proof. There are surely many things I missed, and even misinterpreted, but it is always satisfying to chase some vague connection the application to its theoretical foundation and gradually discovering the missing links in the process.

[1] Zero knowledge proof reference documentation. https://github.com/zkpstandard/zkreference

[2] FS NIZK. https://en.wikipedia.org/wiki/Fiat-Shamir_heuristic

[3] KeyForge. https://www.usenix.org/system/files/sec21summer_specter-keyforge.pdf

[4] Off-the-record communication, or, why not to use PGP. https://dl.acm.org/doi/10.1145/1029179.1029200

[5] https://blog.cryptographyengineering.com/2020/11/16/ok-google-please-publish-your-dkim-secret-keys/