Soundness of Non-Interactive Arguments(2/2)

1Equivalence of the Non-Adaptive Soundness Notions

We now show that the non-adaptive soundness definitions are all equivalent if we allow the malicious provers to be non-uniform:

Theorem : For non-uniform (malicious) provers, a non-interactive argument has non-adaptive/exclusive soundness iff it has non-adaptive/non-uniform soundness, and has non-adaptive/nonuniform soundness iff it has non-adaptive/penalizing soundness.

: Non-adaptive/exclusive soundness follows directly from non-adaptive/penalizing soundness, therefore we only need to show that non-adaptive/non-uniform soundness follows from non-adaptive/exclusive soundness and that non-adaptive/penalizing soundness follows from non-adaptive/non-uniform soundness.

We start by by showing non-adaptive/non-uniform soundness follows from non-adaptive/exclusive soundness. Let Setup be the non-interactive argument in question. Assume that there exists a successful malicious prover against the non-adaptive/non-uniform soundness, i.e., for any negligible function there exists an such that

where the probability is over crs Setup , as well as 's and V's randomness.

We can now construct a malicious prover against non-adaptive/exclusive soundness as follows: We define the first-stage algorithm to choose of length non-uniformly, such that 's success probability is maximized. The state st is left empty. Further, the second-stage algorithm merely calls internally, ignoring the state st. Then, the success probability of is at least as large as the one of and thus non-negligible.

Next, we show that non-adaptive/penalizing soundness follows from non-adaptive/non-uniform soundness.

Assume that there exists a successful malicious prover against the non-adaptive/penalizing soundness, i.e., for any negligible function there exists an such that

where the probability is over as well as V's internal randomness.

We can now construct a malicious prover against non-adaptive/non-uniform soundness as follows: For each input length , we fix the pair , on which 's success probability is maximized (we bound the length of st by 's running time).

Next we define as follows: On input checks whether equals , and if that is the case, it internally calls to generate a proof. Otherwise, returns an empty proof.

Note that we use the non-uniformity to save the sequence of for each input length. It is again easy to see that this prover is indeed a successful malicious prover against non-adaptive/non-uniform soundness.

For adaptive soundness, Arte and Bellare [AB20] showed that there exists a protocol that provides adaptive/exclusive soundness but not adaptive/penalizing soundness. This indicates that a NISZK protocol with adaptive/exclusive soundness might indeed be achievable, compared to one with adaptive/penalizing soundness, for which Pass [Pas16] showed a black-box impossibility result.

Vivek Arte and Mihir Bellare. Dual-mode NIZKs: Possibility and impossibility results for property transfer. Cryptology ePrint Archive, Report 2020/629, 2020. https://eprint.iacr.org/2020/629.

Rafael Pass. Unprovable security of perfect NIZK and non-interactive non-malleable commit- ments. Comput. Complex., 25(3):607–666, 2016.

2Exclusive Soundness Implies Culpable Soundness

In this section we show that adaptive/exclusive soundness implies the notion of adaptive/culpable soundness of [GOS12].

For an -relation let be an -relation for the complement of , i.e., means that there is a polynomial size such that Note that the relation is efficiently verifiable as an -relation (and is therefore in .

Definition  (Adaptive/Culpable Soundness) A non-interactive argument for an relation (in the common reference string model) has adaptive culpable soundness if for any PPT algorithm there exists a negligible function such that

where the probability is over , and 's internal randomness.

A non-interactive argument for an -relation (in the common reference string model) which has a corresponding relation and is adaptive/exclusive sound is also adaptive/culpable sound.

. Assume that we have a successful prover against culpable soundness. We construct a malicious prover against exclusive soundness as follows.

receives as input crs and forwards this to which, then, outputs Our prover checks in polynomial time if If not it immediately outputs , else it returns .

Note that since we interpret outputs as our prover only outputs values not in the language. It is thus an admissible attacker against exclusive soundness. Furthermore, can only win for such that only outputting for those cannot decrease the success probability. This yields that has the same success probability as .