Efficient Concurrent n{sup}(poly(log n))-Simulatable Argument of Knowledge

摘要

In [16], Pass generalized the definition of zero knowledge proof and defined n{sup}(O(σ(n)))-simulatable proof which can be simulated by a simulator in n{sup}(O(σ(n))) time. Assuming the existence of one-way permutation secure against sub-exponential circuits and 2-round perfect hiding commitment scheme, an efficient 4-round perfect n{sup}(poly(log n))-simulatable argument of knowledge was presented there. In this paper, we construct an efficient concurrent n{sup}(poly(log n))_ simulatable argument of knowledge under more general assumption. The new scheme is 5-round and is based on the existence of one-way permutation secure against sub-exponential circuits. However, for the scheme in [16], if using ordinary ∑-protocol for the corresponding statement as sub-protocol, instead of ∑-protocol with honest verifier perfect zero knowledge, the resulting protocol is not necessarily closed under concurrent composition.