# complex zero-knowledge proof?

From: Sebastian Faust (sfaust_at_despammed.com)
Date: 06/13/05

Date: Mon, 13 Jun 2005 17:39:04 +0200



Hi,

I don't know maybe the zk-proof I am searching for, is quite easy to
construct, but sadly till now I couldn't find any solution to my problem.

So my problem is the following:
Let g be a generator of a group G with prime order p. Let further be h,
A \in G and s \in Z_p.

A prover P has 2 secrets s and A, the values h, g and p are publicly known.
P now sends to a verifier V the following values:
c_1 = h^s * g^A
c_2 = h^s * g^{A^2}
c_3 = h^s * g^{A^3}
and now wants to prove in zero-knowledge to V, that
1. she uses her secret s as the exponent of the generator h and
2. the values c_i are constructed by multiplying h^s with g^{A^i}.

That means P wants to prove to V, that the "structure" of her sended c_i
values is "correct".

The problem of proving the correctness of c_1 is quite easy:
P sends c_1 and B = g^A*r^s and r to V. Then V can calculate:
c_1/B = (h^s)/(r^s) = (h/r)^s. Cause V knows (h/r) it is easy for P to
prove to V that she knows the discrete log of c_1/B. Can I transfer this
idea somehow to my original probelm? Or is there any other solution for
proving such things?
Maybe it's mathematically not possible, then I would be quite happy, if
you would tell me, so that I could stop thinking about that problem and
have some sleep again ;).

Bye and thanks,
Sebastian