Soundness of Non-Interactive Arguments(1/2)
Soundness of a non-interactive argument assures that a (computationally-bound) malicious prover is unable to convince the verifier of a false statement.
Commonly, soundness is defined in two variants: Adaptive soundness, with allows the (possibly malicious) prover to chose the statement to prove before seeing the common random string , and non-adaptive soundness, in which the prover has to decide on the statement before the common random string is generated.
Remarkably, there is another dimension of definitional choice for soundness which often goes unnoticed in the literature. This dimension refers to the question how we measure success of the malicious prover. Clearly, the malicious prover should not make the verifier accept for a statement not in the language. But there are two possibilities to capture the non-membership requirement.
One is to disallow to output at all. The other one is to declare to lose if it picks . We call the former stipulation of outputting only exclusive, because it excludes certain adversaries. The latter is called penalizing as it punishes if it chooses .
1Soundness Definitions
In total, we define five soundness notions: adaptive vs. non-adaptive, and exclusive vs. penalizing, as well as a non-uniform variant that only exists for the non-adaptive case.
It is also easy to see that adaptive soundness implies non-adaptive soundness in both settings, and penalizing soundness implies exclusive soundness in any of the other dimensions. The latter is easy to see because any malicious prover breaking exclusive soundness must output such that this prover also satisfies the winning condition in the penalizing setting.
The difference between exclusive and penalizing soundness may appear to be insignificant. Indeed, for non-interactive proofs it is folklore to show that the weakest one of the five notions, non-adaptive/exclusive soundness, implies the strongest one, adaptive/penalizing soundness. See for instance [Gol06]. This may explain why today's literature mostly distinguishes between the (exclusive) non-adaptive notion and the (penalizing) adaptive notion. An exception is the seminal paper by Blum et al. [BDMP91] which defines the adaptive version according to the exclusive dimension. We emphasize, however, that the equivalence of all notions is not known to hold for non-interactive arguments.
Is a more fine-grained distinction between exclusive and penalizing soundness in arguments necessary? We argue that it is. Roughly, the difference is that in the exclusive case the malicious prover (and any other party) knows that its output is not in the language, in the penalizing case even the prover may itself be oblivious about this. This is an important ingredient in Pass' impossibility result to build adaptive sound and adaptive statistical zero-knowledge arguments based on black-box reductions [Pas16]. The result crucially relies on the malicious prover choosing a (random or pseudorandom) statement for which it does not know the status. In other words, this impossibility results rules out the strongest form of adaptive/penalizing soundness.
Rafael Pass. Unprovable security of perfect NIZK and non-interactive non-malleable commitments. Comput. Complex., 25(3):607–666, 2016.
We next argue that the weaker form of adaptive/exclusive soundness is very relevant. It is easy to see that this notion implies a slightly weaker notion of adaptive/culpable soundness [GOS12]. This notion is similar to our definition of adaptive/exclusive soundness, but also requires the malicious prover to output an efficiently verifiable witness (denoted in [GOS12]) that the statement is not in the language . Our exclusive notion asks to output . We prove the implication that adaptive/exclusive yields adaptive/culpable soundness.
Jens Groth, Rafail Ostrovsky, and Amit Sahai. New techniques for noninteractive zero- knowledge. J. ACM, 59(3):11:1–11:35, 2012.
The noteworthy fact is that adaptive/culpable soundness suffices for many applications. One of the most important ones is the possibility to derive universally composable NIZK argument [GOS12]. Other applications include correctness proofs for shuffles [GL07, FL16, FLSZ17] or for e-voting [CG15]. Since adaptive/exclusive soundness implies adaptive/culpable soundness, any protocol satisfying the exclusive notion is also applicable in such settings.
Definition (Soundness of non-interactive Arguments) non-interactive argument for an relation (in the common reference string model) is a triple of probabilistic polynomial-time algorithms Setup, satisfying the completeness as well as at least one of the soundness conditions:
Non-Adaptive/Exclusive Soundness: For every (possibly malicious) probabilistic polynomial-time prover outputting only there exists a negligible function such that for every we have where the probability is over , , as well as , and 's randomness.
Non-Adaptive/Penalizing Soundness : For every (possibly malicious) probabilistic polynomial-time prover there exists a negligible function such that for every we have where the probability is over , as well as , and 's randomness.
Adaptive/Exclusive Soundness: For every (possibly malicious) probabilistic polynomial-time prover outputting only there exists a negligible function such that for every we have where the probability is over , and 's randomness.
Adaptive/Penalizing Soundness: For every (possibly malicious) probabilistic polynomial-time prover there exists a negligible function such that for every we have where the probability is over , and 's randomness.
Non-Adaptive/Non-Uniform Soundness: For every (possibly malicious) probabilistic polynomial-time prover there exists a negligible function such that for every and every with , we have where the probability is over , and , and 's randomness.