We establish new lower bounds and impossibility results for non-interactive zero-knowledge proofs and arguments with set-up assumptions.
– For the common random string model, we exhibit a lower bound for the trade-off between hardness assumptions and the length of the random string for non-interactive zero-knowledge
. This generalizes a previous result ruling out non-interactive zero-knowledge proofs for non-trivial languages with a random string of length
– In the registered public key model, we show that there does not exist a non-interactive zero-knowledge
for a non-trivial language.
– In the bare public key model with fully nonuniform simulation wherein the size of the simulator is also allowed to depend on the size of the distinguisher and the distinguishing gap, there does not exist a non-interactive zero-knowledge
-complete language, unless the polynomial hierarchy collapses. On the other hand, there is a non-interactive zero-knowledge
for all of
with a fully nonuniform simulator.
Our negative results complement upper bounds and feasibility results from previous work.