[Cryptography] Is Non-interactive Zero Knowledge Proof an oxymoron?

[Ron Garret]

On Mar 13, 2016, at 10:31 AM, Benjamin Kreuter <brk7bx at virginia.edu> wrote:

> On Sat, 2016-03-12 at 08:47 -0800, Ron Garret wrote:
>> On Mar 11, 2016, at 9:23 PM, Charlie Kaufman <charliekaufman at outlook.
>> com> wrote:
>> 
>>> 
>>> Often these digital signature schemes are called "Non-interactive
>>> Zero Knowledge Proofs", which seems to me very wrong. If Bob
>>> receives a Non-interactive Zero Knowledge Proof from Alice, he
>>> *can* prove to a third party that the message came from Alice, and
>>> he could not have generated the entire conversation himself.
>> No, because a NIZKP assumes that Bob and Alice share a common
>> reference string drawn from a random distribution, which is the basis
>> for the proof.  The proof doesn’t work between Bob and Charlie
>> because Bob and Charlie don’t share that common reference string.
> 
> That is not true; NIZKs can also exist in the random oracle model.

The same thing happens in the RO model.  Here’s the relevant passage from the paper [1] that you cited:

"We note that an important part of the intuition behind zero-knowledge is lost in these two models in a multi-party scenario, if the CRS string or the random oracle may be reused. An easy way of seeing this is simply by noting that non-interactive zero-knowledge proofs are possible in both these model. A player having received a non-interactive proof of an assertion, it could not have proved before the interaction, can definitely do something new: it can simply send the same proof to someone else. This fact may seem a bit counter-intuitive since the intuition tells us that the simulation paradigm should take care of this. We note, however, that the simulator is much “stronger” in these models than in the plain model. As it is, the simulator is allowed to choose the CRS string, or random oracle, and this fact jeopardizes the zero-knowledge intuition. In fact the zero-knowledge property in these model only guarantees that the verifier will not be able to do anything without referring to the CRS string or the random oracle, it could not have done before.”

So I’m pretty certain that this:

> If Bob receives a Non-interactive Zero Knowledge Proof from Alice, he *can* prove to a third party that the message came from Alice, and he could not have generated the entire conversation himself.


is not true.

rg

[1] Rafael Pass, On Deniability in the Common Reference String and Random Oracle Model.