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

Benjamin Kreuter brk7bx at virginia.edu
Sun Mar 13 13:31:12 EDT 2016


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 NI part of NIZKP is slightly misleading because some interaction
> between Bob and Alice is required to establish the CRS between then.

Actually the CRS needs to be handed down from above, which is what
gives the CRS model its power.

The real point here is that the definition of "zero knowledge" is that
a simulator exists and that it can produce a convincing transcript of
the protocol.  In both the RO and CRS security models, the simulator
has extra power:  to simulate the RO or to generate the CRS.  That is
what makes NIZKs possible in those models, but it also undermines the
intuition behind the security definition.

-- Ben
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160313/9f690341/attachment.sig>


More information about the cryptography mailing list