multi-theorem vs single-theorem for non-interactive zero knowledge

Question

I am trying to understand the definition of zero knowledge for non interactive zero knowledge (signature of knowledge). Sometimes I find multi-theorem zero knowledge, sometimes I find single-theorem. What's the difference ?

My main task is to show that a Zero Knowledge Signature of Knowledge which is zero knowledge (for one signature) is zero knowledge for several signatures. In other words, if you don't reveal anything by signing one message, you don't reveal anything if many people sign many documents with this ZKSoK.

Answer 1

In a zero-knowledge proof system, there are three main properties to be satisfied: completeness, soundness (knowledge soundness for zkpok), and zero-knowledge (or weaker notion such as witness indistinguishability).

one of soundness and zero-knowledge is computationally error-bounded, i.e. you can either than a (computational soundness + statistical zk) combo which is known as ZK Argument, OR a (statistical soundness + computational zk) combo which is referred as ZK Proof.

At the beginning of the protocol, there's usually a Setup step where proving keys and verification keys are generated based on the security parameter given. In NIZK, these proving keys and verification keys are part of the Common Reference String (CRS).

Depending on the construction, repetition of the protocol (i.e. run the protocol multiple times under the same proving and verification key) might hurt soundness or zero-knowledge. "hurt" as in the error bound just increase, making it prone to violation. For some proof system, repetition might violate the property and thus totally break the protocol.

single-theorem basically guarantee those three properties and their error bound for a single round.

multi-theorem basically mean reusing proving & verification keys from Setup for unbounded number of rounds/repetition/theorem without compromising the soundness or zk. (i.e. reuse CRS for many $x \in L$)