Improved Efficient Arguments (Preliminary Version)

We consider complexity of perfect zero-knowledge arguments [4]. Let T denote the time needed to (deterministically) check a proof and let L denote an appropriate security parameter. We introduce new techniques for implementing very efficient zero-knowledge arguments. The resulting argument has the following features: The arguer can, if provided with the proof that can be deterministically checked in O ( T ) time, run in time O ( TL ^{O (1)}). The best previous bound was O ( T ¹⁺ L ^{O (1)}). The protocol can be simulated in time O ( L ^{O (1)}). The best previous bound was O ( T ¹⁺ L ^{O (1)}). A communication complexity of O ( L lg L ), where L is the security parameter against the prover. The best previous known bound was O ( L lg T ).This can be based on fairly general algebraic assumptions, such as the hardness of discrete logarithms.Aside from the quantitative improvements, our results become qualitatively different when considering arguers that can run for some super-polynomial but bounded amount of time. In this scenario, we give the first arguments zero-knowledge arguments and the first "constructive" arguments in which the complexity of arguing a proof is tightly bounded by the complexity of verifying the proof.We obtain our results by a hybrid construction that combines the best features of different PCPs. This allows us to obtain better bounds than the previous technique, which only used a single PCP. In our proof of soundness we exploit the error correction capabilities as well as the soundness of the known PCPs.