A High-Moment Forking Lemma for Sigma-Protocols
We introduce our high-moment forking lemma for establishing tighter security guarantee for -protocols.
Given a -protocol for a relation , we follow the approach underlying the forking lemma [PS00], and show that any malicious prover can be transformed into an algorithm that takes as input an instance and produces (with a certain probability) two accepting transcripts and for such that . Assuming that has special soundness, these two transcripts can then be used to retrieve a witness such that .
However, unlike existing variants of the forking lemma, we design our algorithm with the goal of optimizing the trade-off between its success probability and the th moment of its running time.
Assuming that is a -moment -hard relation , this trade-off leads to an upper bound on the success probability of the malicious prover .
At a high level, given a malicious prover that runs in time and convinces the verifier with probability , the description of our algorithm is quite intuitive.
First, it invokes the malicious prover to obtain a transcript of the protocol.
Then, if this transcript is accepted by the verifier, it rewinds the malicious prover times, providing it with randomly sampled challenges and obtaining respective responses If any one of these additional transcripts is accepted by the verifier and , then the algorithm successfully retrieves a witness.
We prove that the algorithm has success probability roughly , and the -th moment of its running time is at most .
Thus, assuming that is a -moment -hard relation leads to the bound on the probability of a -time malicious prover to convince the verifier.
We say that is -moment -hard with respect to a distribution if for every algorithm it holds that
Formally, we prove the following theorem:
Theorem. Let and be functions of the security parameter , and let be a -protocol with -time special soundness for a relation If is -moment -hard with respect to a distribution then for any malicious prover that runs in time it holds that
for all sufficiently large , where the probability is taken over and , and where denotes the running time of the algorithm denotes the size of the challenge set for any
. Let , and for any let where and (without loss of generality we assume that is deterministic given st). Let , and consider the following algorithm :
The following lemma establishes a lower bound on the success probability of the algorithm :
Lemma 1. For any it holds that either or .
.
Whenever the algorithm reaches Step 3 the witness extraction algorithm guarantees that . Therefore,
where and for every and we assume without loss of generality that for any and for any , st produced by it holds that the state st consists of and (in addition to any other information determined by .
In what follows, for every state , let denote the lexicographically first for which If no such exists, let . It thus holds that
where for every state , the probability is taken only over the choice of .
Then, for every fixed state , the events and are independent, and therefore
where for each .
Denoting for every , we obtain
Claim. It holds that
Given Claim, it holds that either or , and this concludes the proof of Lemma 1.
The following lemma establishes an upper bound on the th moment of the running time of the algorithm (recall that denotes the random variable corresponding to the running time of on input where
Lemma 2. For any it holds that
. The description of yields that with probability it runs in time at most , and with probability it runs in time at most (for simplicity we assume that the time required for sampling a uniform is subsumed by . Therefore,
where Eq. (1) follows from the fact that (and thus .
Equipped with Lemma 1 and Lemma 2, the assumption that is a -moment -hard relation with respect to the distribution implies that either or
Our choice of guarantees that , and therefore
leading to
Therefore, overall we obtain