When reading about the comparison of interactive and non-interactive Zero-Knowledge-Proofs, I came across the statement that non-interactive Zero-Knowledge-Proofs are not deniable compared to interactive ones.
What makes an interactive Zero-Knowledge-Proof deniable, and how is that property lost when transforming it into a non-interactive one?
(e.g., using Fiat-Shamir transform)
Let's begin with interactive ZKPs: the Zero-Knowledgeness is proved by the existence of a Simulator able to produce a transcript indistinguishable from the one obtained by the actual ZKP execution, even if the Simulator doesn't know the witness (so the secret data) held by the Prover. So the Simulator can "cheat": but to be able to do that, it has "superpowers", essentially meaning it doesn't need to respect the rules given by the protocol for messages exchange between parties.
So an interactive ZKP is said to be deniable to third parties not taking part in the actual proof (and only checking the proof transcript after maybe protocol execution) because someone interested in denying the proof could always pretend that the transcript is just the one coming from the Simulator: interactive ZKPs are deniable to third parties because they are non-transferable, given their magic relies on "live" messages exchange following protocol rules.
Non-interactive ZKPs exist because it's damn useful to have a protocol not mandating Prover and Verifier online at the same time, so the transcript is just a bunch of messages the Prover leaves online for when the Verifier will check it: so it's trasferable by design, but of course this means the Prover cannot deny the proof once it has published it (otherwise the proof would be useless ;-) )
Why the transcript produced by Simulator-trick doesn't work for e.g. Fiat-Shamir NIZK? Because in that case the Simulator needs to program the Random Oracle, and in that model the Random Oracle is a single external entity called by both the Prover and the Verifier; however implementations (here the heuristic side of Fiat Shamir) use hash functions as RO, appearing in Prover and Verifier as independent instances of the same algorithm. And we have also said that Verifier could appear after a long time, so: independent instances, not online at the same time: in our real world the Simulator really cannot influence Verifier's hash programming it.
So our "out of the protocol rules" Simulator here is an entity very far from our implementation of the model, but that difference between the ideal model and the real world doesn't influence transcripts' statistical indistinguishability, so that's enough to prove Zero-Knowledgeness; while the real world hashes take care of non-deniability (the verifier with "unprogrammed" hash cannot agree on Simulator's transcript): the previous "by design" is here, as a side effect. Of course this open a huge hole about security of actual Fiat-Shamir implementations, but I guess it's another matter...
The essence of the Fiat-Shamir transform is to ensure that the value of a challenge cannot be known prior to the prover committing to a certain value. If the challenge is provided first, then anyone can forge a signature, and so the signature is deniable.
For an interactive proof, if a verifier cannot prove that they sent a random challenge prior to receiving the response, then the prover can deny that they knew the private key and can therefore deny they provided the signature.
In contrast, if it were a non-interactive proof, the way in which the challenge is calculated will prove that it could not have been known prior to the response value being calculated.
For example, an interactive EC Schnorr proof would involve the prover picking a blinding factor $a$, providing the commitment $A=aG$ to the verifier, and receiving a challenge $c$.
The prover then sends the response $r=a-cx$ for the public key $X=xG$, and the verifier checks that $A\overset{?}{=}rG+cX$.
If the verifier sent the challenge $c$ prior to receiving the commitment $A$, then someone without knowledge of the private key $x$ could just pick a random response $r$ and calculate the value $A=rG+cX$.
Therefore, the verifier cannot produce the values $A$, $c$ and $r$ as proof to a third party that the signature is valid, unless they can prove they only sent $c$ after $A$ was received.
However, with a non-interactive EC Schnorr proof, $c=H(m\mathbin\| aG)$, and the response, as before, is $r=a-cx$.
This means that $c=H(m\mathbin\| aG)=H(m\mathbin\| rG+cP)$. If the prover chose $a$ first, then they would not have control over $c$ and could not produce a valid value of $r$ without knowledge of the private key. Similarly, if the prover chose $r$ first, they could not have produced a valid value of $A$ without knowledge of the private key. Either way, the prover would have had to have chosen an $a$ or $r$ value prior to discovering the value of the challenge $c$, which means they must have known the private key in order to produce the signature $(A, r)$.
