0
$\begingroup$

If OWFs exist, then a Shared Random String for
NIZK proofs (of membership) can be established by:

verifier commits a random string of the same length using statistically hiding commitment
prover sends random string of the same length
verifier opens the commitments
the xor of the commited bits and the prover's string is used as the shared random string


The problem with using this for NIZK proofs of knowledge is that the
above protocol is not (at least not obviously) simulable for the prover.


Is there a known concrete obstacle to being able to establish
a Shared Random String for NIZK proofs of knowledge?
(For example, showing that such a protocol can't be black-box zero knowledge?)

If no, is there a plausible computaional assumption that is known to suffice for doing so?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I'm not sure the solution you have given works.

However, it can be adapted to work -- both for NIZK proofs and proofs of knowledge -- by using a coin-tossing protocol where "secure" here means in the sense of general secure two-party computation. This can be done based on one-way functions in polynomially many rounds, or based on stronger assumptions in constant rounds.

A good reference is Lindell's paper on coin tossing.

Improve this answer
$\endgroup$
1
  • $\begingroup$ That certainly seems to work. $\:$ (Unless someone else gives a better answer, $\hspace{1.6 in}$ I'll be accepting and upvoting this.) $\;\;$ $\endgroup$
    – user6973
    Mar 22, 2012 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.