Zero knowledge definitions / additive zero knowledge

[Amitabh]

Hi, I have been trying to understand the following types of zero knowledge proofs.. I would be grateful if someone could explain their meaning in layman terms:

1. Concurrent zero knowledge
2. Resettable zero knowledge
3. Non-malleable zero knowledge

Thanks

[JustinT]

Let's see if a brief defining of terms will help clarify the general approach of each term, all of which are quite extensive. First, let's look at concurrent zero-knowledge. Basically, you have a verifier, which we'll assume to have malicious intent. Let's suppose this verifier is capable of interacting with a prover, numerous times, in what you might refer to as an interleave. During each of these interactions, the prover makes use of a fresh random tape.

In resettable zero-knowledge however, it enforces, for each interaction, that the prover is using same random tape. Depending on the particular model, be it public-key or not, a resettable zero-knowledge protocol could, but isn't required to, be built with the foundational basis of a concurrent zero-knowledge protocol. This could be considered a "stronger" notion, than concurrent zero-knowledge.

When we look at non-malleable zero-knowledge, we can basically sum the criteria as follows, where A is an adversary, A' is a simulator of an adversary (both polynomial time-bounded), and R is a relation approximator (computable in polynomial time): For every A, an A' exists, such that for every R |pi (A,R) - pi' (A',R)| is subpolynomial. That's the "security" notion, in other words. Using string commitment, you can instantiate pretty much any zero-knowledge situation in a non-malleable manner.

Dwork, Naor, and Sahai, Canetti, Goldreich, Goldwasser, and Micali, and Feige, Fiat, and Shamir, have published quite a bit of interesting analysis of both concurrent and resettable zero-knowledge protocols, and have explored, also, the intimacy of non-malleability within zero-knowledge proofs. Have you researched any of their works? If not, I'll be glad to harvest a few good, extensive papers. It's almost essential that you understand the theory, to understand the definitions above.
_________________
"Strict Avalanche Criterion n. Restrictive clause in ski-insurance policy."

[Amitabh]

Hi Justin,

Thanks for the explanation. I have been reading papers of some of the people you mentioned but some of the concepts are still not very clear.
I would appreciate if you could provide me with some good references.

BTW I have been working on the concept of 'additive' zero knowledge, which is roughly defined in the following papers:

http://homepage.cs.latrobe.edu.au/asaxena/saxena05auth.pdf
http://homepage.cs.latrobe.edu.au/asaxena/saxena05novel.pdf

The first paper explains the concept while the second paper, in an intuitive way, gives an existence proof.

An additive NIZK proof is based on the idea that a verifier can create a different proof using an old proof in such a way that the zero-knowledge property is preserved.

I would appreciate some feedback.

Cheers.

[JustinT]

Sure, no problem. I'm not sure which papers you have reviewed, but here is a very extensive list of references on zero-knowledge-based proofs and protocols, including those by the authors I mentioned in my previous post; many are available for download in a multitude of various formats. Here, also, is a fragment from some of Oded Goldreich's publications, including a nice, lengthy section on zero-knowledge, and more.

Perhaps that will give you something more to work with. I'll see what else I can find. As for your research paper, I am still in the midst of looking over it. It is interestingly novel, yet genius, with extensions to other, published aspects of proofs under the zero-knowledge definition, that we've seen before. Quite an original read, it is, and good research to keep me up-to-date with zero-knowledge protocols, since that's not my dedicated area of cryptographic research. I'll keep reading, but until then, it's looking informative! Cheers.
_________________
"Strict Avalanche Criterion n. Restrictive clause in ski-insurance policy."