Additive Zero Knowledge

[Amitabh]

I have been working on the concept of 'additive' zero knowledge, which
is roughly described 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 sort of 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 if anyone could give some feedback.

Regards
Amitabh

[Amitabh Saxena]

In addition to my above post...

I observed that the notion of additive zero knowledge used for chaining
digital signatures closely resembles the concept of 'sequential'
composition of interactive proofs (discussed for example in the paper
[On the Composition of Zero-Knowledge Proof Systems] by Goldreigh and
Krawczyk).

In my system, however, I want the interaction between the provers and
verifiers to be completely eliminated. Thus, if A, B and C are users in
a chain, A should prove knowledge of some fact to B
(non-interactively), who in turn proves knowledge of A's claim to C
(also non-interactively). I would like to formalize this concept
mathematically and would appreciate some feedback on this.

(It may be that there is a flaw in my reasoning and such a proof system
is not possible.)

Rgds
Amitabh

Post by Amitabh
I have been working on the concept of 'additive' zero knowledge, which
http://homepage.cs.latrobe.edu.au/asaxena/saxena05auth.pdf
http://homepage.cs.latrobe.edu.au/asaxena/saxena05novel.pdf

[David Wagner]

I have been working on the concept of 'additive' zero knowledge, [...]

Let me see if I understand the problem, by giving an example.

Everyone knows Verisign's public RSA key (n,e). Alice wants to convince
Bob that she knows a factor of n. She can do so with a non-interactive
zero-knowledge proof (NIZKP) of knowledge of a factor q of n:
Alice -> Bob: s = pf(exists q in Z such that q | n and 1<q<n)
(Here pf(.) denotes a proof of knowledge.) Bob can check that he is
convinced by executing some verification algorithm, call it V. In other
words, Bob accepts iff V(n,s) = true.

Bob now wants to convince Carol that he knows some value t such that,
if only he told her this value, she would be willing to accept as a NIZPK
of knowledge of a factor of n. In other words, Bob wants to convince Carol
that he knows a bitstring t such that V(n,t) = true. In particular, we are
looking for a NIZKP of knowledge of such a value t.

Did I understand the problem you are trying to solve correctly?

If so, it seems straightforward at least in principle. The verification
algorithm V is some polynomial-time algorithm. Thus, the condition that
t be such that V(n,t) = true is a condition that can be computed in
polynomial time. In particular, the statement that n is such that there
exists t satisfying V(n,t)=true is a NP-statement, and we know that every
NP-statement has a ZKP. In an appropriate model (e.g., the random oracle
model; the common reference string model), this statement also has a NIZKP
of knowledge. So why don't we just have Bob provide Carol with a NIZKP of
knowledge of such a t?
Bob -> Carol: s' = pf(exists t in {0,1}^* such that V(n,t) = true)
Does this work? It might not be terribly efficient in practice (though
still polynomial-time), but it seems straightforward if all you care about
is polynomial running time.