Precise zero-knowledge arguments with poly-logarithmic efficiency

Precise zero-knowledge was introduced by Micali and Pass in STOC’06. This notion captures the idea that the view of a verifier can be reconstructed in almost same time. Following the notion, they constructed some precise zero-knowledge proofs and arguments, in which the communicated messages are polynomial bits. In this paper, we employ the new simulation technique introduced by them to provide a precise simulator for a modified Kilian’s zero-knowledge arguments with poly-logarithmic efficiency (this modification addressed by Rosen), and as a result we show this protocol is a precise zero-knowledge argument with poly-logarithmic efficiency. We also present an alternative construction of the desired protocols.