Constant-Round Restricted-Verifier Zero-Knowledge with Polynomial Precision
Ning Ding, Dawu Gu · 2007
We provide the first proof of that for every language L isin NP there exists an O(1)-round computational zero-knowledge argument with polynomial precision for L. Our result assumes that ratio of running-time of any adversary verifier in some same verifier round of any two different executions of the argument is bounded by nalpha, where n is secure parameter and alpha is any predeterminate constant. Such verifiers are called restricted verifiers. Precise zero-knowledge was introduced by Micali and Pass in STOC'06 (They used the term "local zero-knowledge" there.) and they constructed some omega(1)-round polynomial/linear precise zero- knowledge protocols for NP and hence left an open problem how to construct O(1)-round polynomial/linear precise zero-knowledge protocols. By providing a precise simulator for Barak's O(1)-round non-black-box zero-knowledge argument, we prove that the argument is polynomial precise.