Additive Zero Knowledge
(too old to reply)
2005-01-18 17:26:52 UTC
I have been working on the concept of 'additive' zero knowledge, which
is roughly described in the following papers:


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.

Amitabh Saxena
2005-02-01 04:32:03 UTC
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

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.)

Post by Amitabh
I have been working on the concept of 'additive' zero knowledge, which
David Wagner
2005-02-10 14:47:18 UTC
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.