A Pedagogically-Optimized Straight-Line Extractor

Table of Contents

1. What is the Point?
2. Preliminaries
3. The Construction
4. Proof of Security

What is the Point?

When using zero-knowledge proofs of knowledge (ZKPoKs) as a tool to construct multi-party computation (MPC) protocols, it is convenient to prove that those ZKPoKs realize ideal functionalities as is typical for MPC tools. Unfortunately, there is often a definitional mismatch. In the context of ZKPoKs, the property of knowledge soundness is defined by the existence of a knowledge extractor, which often relies upon the technique of rewinding the prover. To prove that a ZKPoK realizes an ideal functionality, we must describe a simulator that interacts with the ideal functionality and simulates the view of the prover. In order to supply an input to the functionality, the simulator for the prover's view usually exracts that input from a copy of the prover that it runs internally. However, we often insist upon straight-line simulation, meaning that the simulator must perform the extraction without rewinding its internal prover, and thus the knowledge extractor is not directly helpful. Straight-line simulation is a key component of achieving security under concurrent composition, and straight-line extraction techniques are also important because they enable asymptotically-tight security reductions to be constructed.

To prove that a ZKPoK realizes a functionality, we must also construct a simulator for the view of the verifier. The zero-knowledge property of ZKPoKs guarantees the existence of a simulator for the verifier's view, but it is common for this simulator to rewind an internal copy of the verifier, or else to sample protocol messages out of order (e.g. such that the first message depends upon the second one). This also conflicts with the requirement for straight-line simulation, when it arises.

For many ZKPoKs (and in particular, sigma protocols) there exist straight-line extraction (SLE) compilers that transform the protocols in order to resolve the above mismatches. The most notable examples are the compilers of [Pass03], [Fischlin05], [Unruh15], and [Ks22]. However, these compilers also aim to achieve non-interactivity and therefore make use of random oracles. Interactive SLE compilers without random oracles do exist in the common reference string (CRS) model (for example, [HN10]), but they often require other advanced primitives such as universally-composable commitments. Finally, there exist straight-line-simulatable ZKPoKs that fix specific interactive proof systems as starting points, rather than compiling arbitrary sigma protocols (e.g. [CF01], which is based upon graph hamiltonicity).

When developing my MPC class, I wished to teach an SLE compiler for arbitrary sigma protocols that does not require random oracles or ideal commitments. I could find no such thing in the literature, so I developed the one I will present in this document. It is based upon commitments that are extractable in the CRS model, but not necessarily equivocable, allowing it to be used with simple commitment schemes based upon trapdoor permutations. It is compatible with nearly any variation on the real-ideal security paradigm (even ones that do not support reactive functionalities or concurrent composition), and it does not attempt to achieve non-interactivity, concrete efficiency, or CRS re-use. In other words, I have tried to optimise it for ease of understanding, and to make use of only simple, easy-to-construct primitives.

The intuition behind the construction is simple. A sigma protocol has three rounds: the first is from the prover to the verifier, the second is a challenge from the verifier to the prover, and the prover responds to this challenge in the third. If the prover responds to multiple distinct challenges (for a single first message) in such a way that the verifier would accept the responses, then the responses can be used to compute a witness for the prover's statement. In the real world, no prover would do this, but knowledge extractors often use rewinding to feed multiple challenges to the prover. Our compiler will do something different: before receiving the challenge, the prover in the compiled protocol will commit to responses to all possible challenges, and then open only the appropriate commitment. The commitment scheme enables straight-line extraction by the simulator, and thus the simulator can compute a witness without rewinding. Similarly, the verifier will commit to its challenges at the beginning of the protocol, before the prover sends its first message. This will enable us to use the simulator that is guaranteed to exist for sigma protocols, even though that simulator requires the verifier's challenge (i.e. the second message) to be chosen before the prover's first message. In order to achieve negligible soundness error, the construction will repeat the underlying sigma protocol many times in parallel.

A Note on Novelty

I do not claim that anything here is novel or surprising. The construction I will present is inspired by several prior works (notably [Pass03] and [GK96]), and it is extremely similar to [HN10, Protocol 9], although the security analysis differs substantially due to the fact that ideal commitments are avoided.

Preliminaries

Basics and Notation

A very large amount of background information will not be covered in this document. In particular, the reader will need to have a basic understanding of distributional ensembles and computational indistinguishability, languages and witness relations, interactive proof systems, and zero-knowledge. These topics are covered in depth in [Goldreich04, Sections 3.2 and 4.1-4.3] and in many other textbooks. The goal of this document is to prove a particular protocol secure in the real-ideal paradigm, also known as the simulation-based security paradigm. A version of this paradigm is covered in detail in [Goldreich04, Chapter 7], but the proof presented here holds in many variations, including [Canetti00] and [Canetti01]. The notation used in this document largely follows the conventions of the Universal Composition framework [Canetti01], but note that the protocol is explicitly structured to avoid the need for concurrent composition, and session IDs are omitted.

In this document, $=$ denotes equality, $:=$ denotes deterministic assignment, and $\leftarrow$ denotes assignment by sampling from the distribution produced by a sampling algorithm on the right-hand side. Finally, ${\approx }_{𝖼}$ denotes the computational indistinguishability of two distributional ensembles. In general, $n$ is a security parameter and $\epsilon$ denotes a negligible function.

Sigma Protocols

A sigma protocol $\mathrm{\Sigma }$ is an interactive proof system for language $L$ with witness-relation $R$ comprising the following 3-message interaction generated by four PPT algorithms $(\mathrm{\Sigma }.𝖥𝗂𝗋𝗌𝗍,\mathrm{\Sigma }.𝖲𝖾𝖼𝗈𝗇𝖽,\mathrm{\Sigma }.𝖳𝗁𝗂𝗋𝖽,\mathrm{\Sigma }.𝖵𝖾𝗋𝗂𝖿𝗒)$:

1. The prover samples a commitment $a$ and some secret state $u$ via $(a,u)\leftarrow \mathrm{\Sigma }.𝖥𝗂𝗋𝗌𝗍(x,w)$ and sends the statement $x$ along with $a$ to the verifier.
2. The verifier samples a challenge $e\leftarrow \mathrm{\Sigma }.𝖲𝖾𝖼𝗈𝗇𝖽(x)$ and sends it to the prover.
3. The prover sends a response $z\leftarrow \mathrm{\Sigma }.𝖳𝗁𝗂𝗋𝖽(x,w,u,e)$ to the verifier.
4. The verifier outputs $\mathrm{\Sigma }.𝖵𝖾𝗋𝗂𝖿𝗒(x,a,e,z)$.

The basic properties required of all interactive proof systems are completeness and soundness, for descriptions of which the reader is referred to [Goldreich04, Section 4.2]. For more information about sigma protocols in particular, including special soundness and special honest-verifier zero-knowledge, the reader is referred to [Damgård10]. To avoid confusion with other “commitments” in the protocol we will construct in this document, we will refer to $(a,e,z)$ as the first, second, and third messages of $\mathrm{\Sigma }$.

We will use ${\mathrm{\Sigma }}_n$ to denote a version of $\mathrm{\Sigma }$ that is restricted to accepting statements of exactly length $n$. In other words, if any of the algorithms in ${\mathrm{\Sigma }}_n$ is given $x$ such that $|x|\ne n$, then it does nothing. We will similarly use $L_n$ and $R_n$ to the restrictions of $L$ and $R$ to statements of length $n$.

We will assume that the challenge-sampling algorithm $\mathrm{\Sigma }.𝖲𝖾𝖼𝗈𝗇𝖽$ chooses a challenge uniformly from a set $E_x=\mathrm{image}(\mathrm{\Sigma }.𝖲𝖾𝖼𝗈𝗇𝖽(x))$ that depends only upon the statement $x$, and that the size of $E_x$ is upper-bounded by some polynomial in the statement length. That is, we will assume there exists some polynomial $p$ such that $|E_x|\le p(|x|)$. We will also assume that $\mathrm{\Sigma }.𝖳𝗁𝗂𝗋𝖽$ does nothing if it is given $e\notin E_x$. Finally, we will assume that $\mathrm{\Sigma }.𝖵𝖾𝗋𝗂𝖿𝗒$ is deterministic.

Special Soundness

A sigma protocol $\mathrm{\Sigma }$ is said to be $\ell$-Special-Sound for language $L$ with witness-relation $R$ if and only if there exists an additional PPT algorithm $\mathrm{\Sigma }.𝖤𝗑𝗍$ with the following property:

Suppose that we have $\ell$ transcripts of $\mathrm{\Sigma }$ that share their statement $x$ and first message $a$, but differ in their second message; that is, we have $(x,a,{\{e_i,z_i\}}_{i\in [\ell ]})$ such that $e_i\ne e_j$ if $i\in [\ell ]$ and $j\in [\ell ]$ are distinct. If $\mathrm{\Sigma }.𝖵𝖾𝗋𝗂𝖿𝗒(x,a,e_i,z_i)=1$ for every $i\in [\ell ]$, then $\mathrm{\Sigma }.𝖤𝗑𝗍(x,a,{\{e_i,z_i\}}_{i\in [\ell ]})$ outputs $w$ such that $(x,w)\in R$. For simplicity, we assume that this holds with probability 1, and that $\mathrm{\Sigma }.𝖤𝗑𝗍$ can accept more than $\ell$ transcripts as input.

Note that this property is only meaningful when $\ell \le |E_x|$, and so we will assume this condition holds from now on.

Special Honest-Verifier Zero-Knowledge

A sigma protocol $\mathrm{\Sigma }$ is said to be Special Honest-Verifier Zero-Knowledge (SHVZK) for language $L$ with witness-relation $R$ if there exists an additional PPT algorithm $\mathrm{\Sigma }.𝖲𝗂𝗆$ such that

$${\{(x,a,e,z):(a,u)\leftarrow \mathrm{\Sigma }.𝖥𝗂𝗋𝗌𝗍(x,w),z\leftarrow \mathrm{\Sigma }.𝖳𝗁𝗂𝗋𝖽(x,w,u,e)\}}_{(x,w)\in R,e\in E_x}{\approx }_{𝖼}{\{(x,a,e,z):(a,z)\leftarrow \mathrm{\Sigma }.𝖲𝗂𝗆(x,e)\}}_{(x,w)\in R,e\in E_x}$$

where the distinguishing advantage is considered relative to $|x|$. Note that this differs from ordinary HVZK in that the the simulator works even conditioned on a fixed value of $e$. As a corollary of the above statement of SHVZK, it holds that for every PPT adversary $𝒜$ there exists a negligible function $\epsilon$ such that

$$|\mathrm{Pr}[𝒜(a_b,z_b,s)=b:b\leftarrow \{\mathrm{0,1}\},(x,w,e,s)\leftarrow 𝒜(1^n),(a_0,u)\leftarrow {\mathrm{\Sigma }}_n.𝖥𝗂𝗋𝗌𝗍(x,w),z_0\leftarrow {\mathrm{\Sigma }}_n.𝖳𝗁𝗂𝗋𝖽(x,w,u,e),(a_1,z_1)\leftarrow {\mathrm{\Sigma }}_n.𝖲𝗂𝗆(x,e)]-\frac{1}{2}|\le \epsilon (n)$$

Non-Interactive Commitments

A non-interactive commitment scheme $C$ is a trio of PPT algorithms $(C.𝖦𝖾𝗇,C.𝖢𝗈𝗆,C.𝖮𝗉𝖾𝗇)$ with the following syntax:

• k\leftarrow C.𝖦𝖾𝗇(1^n) takes a security parameter $n$ and outputs a commitment key $k$.
• $(c,d)\leftarrow C.{𝖢𝗈𝗆}_k(m)$ takes some message $m\in ℳ$, where the message space $ℳ$ is assumed to be ${\{\mathrm{0,1}\}}^{\ast }$ unless stated otherwise. It outputs a commitment string $c$ and an opening $d$.
• $m^{\prime }:=C.{𝖮𝗉𝖾𝗇}_k(c,d)$ outputs $m^{\prime }\in ℳ\cup \{\perp \}$, where $\perp$ is a special symbol indicating that $(c,d)$ are invalid with respect to $k$. For simplicity, we assume this algorithm is deterministic.

There are three basic properties that all commitment schemes must achieve:

• Completness and Correctness holds if $\forall m\in ℳ\forall k\in \mathrm{image}(C.𝖦𝖾𝗇)$, we have $C.{𝖮𝗉𝖾𝗇}_k(C.{𝖢𝗈𝗆}_k(m))=m$.
• Hiding holds if for every PPT adversary $𝒜$ there exists a negligible function $\epsilon$ such that

  $$|\mathrm{Pr}[𝒜(c^{\ast },s)=b:b\leftarrow \{\mathrm{0,1}\},k\leftarrow C.𝖦𝖾𝗇(1^n),(m_0,m_1,s)\leftarrow 𝒜(1^n,k),(c^{\ast },d^{\ast })\leftarrow C.{𝖢𝗈𝗆}_k(m_b)]-\frac{1}{2}|\le \epsilon (n)$$

• Binding holds if for every PPT adversary $𝒜$ there exists a negligible function $\epsilon$ such that

  $$\mathrm{Pr}[\perp \ne m\ne m^{\prime }\ne \perp :k\leftarrow C.𝖦𝖾𝗇(1^n),(c,d,d^{\prime })\leftarrow 𝒜(1^n,k),m:=C.{𝖮𝗉𝖾𝗇}_k(c,d),m^{\prime }:=C.{𝖮𝗉𝖾𝗇}_k(c,d^{\prime })]\le \epsilon (n)$$

Trapdoor Straight-Line Extractability for Commitments

A non-interactive commitment scheme $C$ is said to be trapdoor straight-line extractable if there exist two additional PPT algorithms $C.𝖳𝖦𝖾𝗇$ and $C.𝖤𝗑𝗍$ with the following syntax and properties:

• $(k,t)\leftarrow C.𝖳𝖦𝖾𝗇(1^n)$ outputs a commitment key $k$ and a trapdoor $t$. Trapdoor Indistinguishability holds if the keys generated by this algorithm are indistinguishable from ordinary keys; that is, if

  $${\{C.𝖦𝖾𝗇(1^n)\}}_{n\in \mathbb{N}}{\approx }_{𝖼}{\{k:(k,t)\leftarrow C.𝖳𝖦𝖾𝗇(1^n)\}}_{n\in \mathbb{N}}$$

• $m^{\prime }:=C.{𝖤𝗑𝗍}_t(c)$ outputs $m^{\prime }\in ℳ\cup \{\perp \}$, where $\perp$ is a special symbol indicating that extraction has failed. Straight-Line Extractability holds if no adversary is able to generate a commitment under a trapdoored key such that the message extracted using the trapdoor is different from the message opened in the standard way. Specifically, we insist that for every PPT adversary $𝒜$ there exists a negligible function $\epsilon$ such that

  $$\mathrm{Pr}[C.{𝖤𝗑𝗍}_t(c)\ne C.{𝖮𝗉𝖾𝗇}_k(c,d)\ne \perp :(k,t)\leftarrow C.𝖳𝖦𝖾𝗇(1^n),(c,d)\leftarrow 𝒜(1^n,k)]\le \epsilon (n)$$

Note that commitments with this property are easy to construct: for example, they can be built trivially from ElGamal Encryption.

The Zero-Knowledge Functionality

The construction below will realize the standard zero-knowledge functionality ${ℱ}_{𝖹𝖪}^R$ for two parties, where $R$ is the witness relation for some language. For more information, see [CLOS02, Section 6]. The code of the functionality is as follows:

The CRS Model

For the purposes of this exposition, the Common Reference String (CRS) model augments the standard model of cryptography by providing the parties with access to a functionality ${ℱ}_{𝖢𝖱𝖲}$ that honestly samples a public string according to an arbitrary sampling algorithm. In our case, ${ℱ}_{𝖢𝖱𝖲}$ will sample and publish the key for a trapdoor straight-line extractable commitment scheme.

The Construction

Proof of Security

Theorem: If $\mathrm{\Sigma }$ is an $\ell$-special-sound SHVZK sigma protocol for language $L$ with witness-relation $R$, such that the size of the challenge space $E_x$ is always at most polynomial in $|x|$, and if $C$ is a trapdoor straight-line extractable commitment scheme, then the above protocol realizes ${ℱ}_{𝖹𝖪}^R$ with straight-line simulation in the ${ℱ}_{𝖢𝖱𝖲}$-hybrid model in the presence of a malicious adversary that statically corrupts either party.

Since the protocol is asymmetric, we will prove two lemmas, one for each of the two parties that might be corrupted. The theorem follows by the conjunction of these lemmas. Note that the proofs will employ the specific formalism of the UC framework—specifically, they will quantify over environments—but they can easily be adapted to many other variations on the real-ideal/simulation-based security paradigm.

---

Lemma 1: If $\mathrm{\Sigma }$ is an $\ell$-special-sound sigma protocol for language $L$ with witness-relation $R$, such that the size of the challenge space $E_x$ is always at most polynomial in $|x|$, and if $C$ is a trapdoor straight-line extractable commitment scheme, then for every malicious PPT adversary $𝒜$ that statically corrupts the prover, there exists a PPT straight-line simulator ${𝒮}_{𝖯}$ such that for every PPT environment $𝒵$,

$${\left\{{\text{Rᴇᴀʟ}}_{{\pi }_{𝖹𝖪}^{{\mathrm{\Sigma }}_n,C},𝒜,𝒵}(n)\right\}}_{n\in \mathbb{N}}{\approx }_{𝖼}{\left\{{\text{Iᴅᴇᴀʟ}}_{{ℱ}_{𝖹𝖪}^{R_n},{𝒮}_{𝖯},𝒵}(n)\right\}}_{n\in \mathbb{N}}$$

Proof: We will begin by describing the simulator, and then we will argue for the indistinguishability of the real and ideal experiments via a sequence of hybrid experiments.

First Hybrid Experiment and Reduction. Now consider a hybrid experiment ${\text{Hʏʙʀɪᴅ}}_1$ which is exactly like the real-world experiment, except that in Step 1, ${ℱ}_{𝖢𝖱𝖲}$ uses $C.𝖳𝖦𝖾𝗇$ to sample $k_{𝖯}$ instead of $C.𝖦𝖾𝗇$. By a simple reduction to the trapdoor-indistinguishability property of $C$, we can show that

$${\left\{{\text{Rᴇᴀʟ}}_{{\pi }_{𝖹𝖪}^{{\mathrm{\Sigma }}_n,C},𝒜,𝒵}(n)\right\}}_{n\in \mathbb{N}}{\approx }_{𝖼}{\left\{{\text{Hʏʙʀɪᴅ}}_1(n)\right\}}_{n\in \mathbb{N}}$$

Second Hybrid Experiment and Reduction. Consider a second hybrid experiment ${\text{Hʏʙʀɪᴅ}}_2$, which is exactly like ${\text{Hʏʙʀɪᴅ}}_1$ except that the experiment produces output to the environment on behalf of the verifier only if ${\hat{z}}_{i,e_i}=z_{i,e_i}$ where ${\hat{z}}_{i,e_i}:=C.{𝖤𝗑𝗍}_t(c_{i,e_i})$ for every $i\in [r]$. Suppose there is a pair $(𝒜,𝒵)$ that can distinguish ${\text{Hʏʙʀɪᴅ}}_2$ from ${\text{Hʏʙʀɪᴅ}}_1$; they can do so only by contriving to cause ${\hat{z}}_{j,e_j}\ne z_{j,e_j}\ne \perp$ for some $j\in [r]$. We will prove that this event happens with negligible probability via a reduction to the straight-line extractability property of $C$.

The reduction ${ℛ}_{1\to 2}$ plays the straight-line extractability game for $C$ and emulates ${\text{Hʏʙʀɪᴅ}}_1(n)$ internally toward $(𝒜,𝒵)$. In the emulated experiment, ${ℛ}_{1\to 2}$ emits its own challenge key $k$ as $k_{𝖯}$ on behalf of ${ℱ}_{𝖢𝖱𝖲}$ in Step 1, and it halts the experiment upon receiving $(c_{i,e_i},d_{i,e_i})$ for every $i\in [r]$ in Step 7. Note that at this point, the emulated experiment is identically distributed to both ${\text{Hʏʙʀɪᴅ}}_2$ and ${\text{Hʏʙʀɪᴅ}}_1$. ${ℛ}_{1\to 2}$ guesses $g\leftarrow [r]$ and outputs $(c_{g,e_g},d_{g,e_g})$ to the straight-line-extractability game for $C$. With probability $1/r$, it will hold that $g=j$, and if this occurs at the same time that ${\hat{z}}_{j,e_j}\ne z_{j,e_j}\ne \perp$, then the reduction wins the straight-line-extractability game. By the security of $C$ there exists a negligible function $\epsilon$ that upper-bounds the reduction's probability of a win, which implies that for every PPT $(𝒜,𝒵)$,

$$\mathrm{Pr}[\exists j\in [r]\mathrm{s}.\mathrm{t}.{\hat{z}}_{j,e_j}\ne z_{j,e_j}]\le r\cdot \epsilon (n)$$

which is also negligible, and it follows that ${\left\{{\text{Hʏʙʀɪᴅ}}_1(n)\right\}}_{n\in \mathbb{N}}{\approx }_{𝖼}{\left\{{\text{Hʏʙʀɪᴅ}}_2(n)\right\}}_{n\in \mathbb{N}}$.

Ideal-World Experiment and Third Reduction. It remains to show that ${\text{Hʏʙʀɪᴅ}}_2$ is indistinguishable from the ideal-world experiment, which is the main challenge in the proof of Lemma 1. Notice that the distributions of these two experiments are identically distributed in all events except for one: in the event that ${\mathrm{\Sigma }}_n.𝖵𝖾𝗋𝗂𝖿𝗒(x,a_i,e_i,z_{i,e_i})=1$ for every $i\in [r]$ but there exists no $h\in [r]$ such that $C.{𝖤𝗑𝗍}_t(c_{h,e})\ne \perp$ for all $e\in E_x$, the verifier will produce output in ${\text{Hʏʙʀɪᴅ}}_2$ but not in the ideal-world experiment. We will prove that this event happens with at most negligible probability via reduction to the hiding property of $C$.

The reduction ${ℛ}_{2\to 3}^{i^{\ast }}$ is parameterized by a fixed index $i^{\ast }\in [r]$, and it plays the hiding game for $C$ and emulates ${\text{Hʏʙʀɪᴅ}}_2(n)$ internally toward $(𝒜,𝒵)$. ${ℛ}_{2\to 3}^{i^{\ast }}$ emulates the first three steps of the experiment faithfully, except that emits its own challenge key $k$ as $k_{𝖲}$ on behalf of ${ℱ}_{𝖢𝖱𝖲}$ in Step 2. Next, ${ℛ}_{2\to 3}^{i^{\ast }}$ samples $(e_1,\dots ,e_r,{\hat{e}}_0,{\hat{e}}_1)\leftarrow E_x^{r+2}$ and computes $m_0:=(e_1,\dots ,e_{i^{\ast }-1},{\hat{e}}_0,e_{i^{\ast }+1},\dots ,e_r)$ and $m_1:=(e_1,\dots ,e_{i^{\ast }-1},{\hat{e}}_1,e_{i^{\ast }+1},\dots ,e_r)$. The reduction emits $(m_0,m_1)$ to the hiding game, and receives $c^{\ast }$ in response, which it sends to the corrupted prover on behalf of the verifier in Step 4 of the emulated experiment as $c_{𝖵}$. ${ℛ}_{2\to 3}^{i^{\ast }}$ continues emulating until Step 5 is complete, and then ceases: at this point, the emulated experiment is distributed identially to both ${\text{Hʏʙʀɪᴅ}}_2$ and the ideal-world experiment. If there exists $f\in E_x$ and $b^{\prime }\in \{\mathrm{0,1}\}$ such that $f={\hat{e}}_{1-b^{\prime }}\ne {\hat{e}}_{b^{\prime }}$ and $C.{𝖤𝗑𝗍}_t(c_{i^{\ast },f})=\perp$, then the reduction outputs $b^{\prime }$; otherwise, it outputs a uniformly random bit.

Next, let us calculate the probability that ${ℛ}_{2\to 3}^{i^{\ast }}$ outputs $b^{\prime }=b$, where $b$ is the value sampled uniformly by the hiding game for $C$. Let ${𝖣𝗂𝗌𝗍𝗂𝗇𝗀𝗎𝗂𝗌𝗁}_{i^{\ast }}$ be the event that $\exists f\in E_x\mathrm{s}.\mathrm{t}.f\ne e_{i^{\ast }}\wedge C.{𝖤𝗑𝗍}_t(c_{i^{\ast },f})=\perp$. Note that $(𝒜,𝒵)$ can successfully distinguish ${\text{Hʏʙʀɪᴅ}}_2(n)$ from the ideal-world experiment only if $𝖣𝗂𝗌𝗍𝗂𝗇𝗀𝗎𝗂𝗌𝗁={\bigwedge }_{i\in [r]}{𝖣𝗂𝗌𝗍𝗂𝗇𝗀𝗎𝗂𝗌𝗁}_i$ occurs. Let $𝖱𝖾𝖽𝗎𝖼𝖾$ be the event that $f={\hat{e}}_{1-b}\ne {\hat{e}}_b$ for an arbitrary $f\in E_x\setminus \{e_{i^{\ast }}\}$ (and note that since the three values are independently chosen, the specific value of $f$ does not matter). Note that ${ℛ}_{2\to 3}^{i^{\ast }}$ always outputs $b^{\prime }=b$ when ${𝖣𝗂𝗌𝗍𝗂𝗇𝗀𝗎𝗂𝗌𝗁}_{i^{\ast }}\wedge 𝖱𝖾𝖽𝗎𝖼𝖾$ occurs, but when ${𝖣𝗂𝗌𝗍𝗂𝗇𝗀𝗎𝗂𝗌𝗁}_{i^{\ast }}\wedge \neg 𝖱𝖾𝖽𝗎𝖼𝖾$ or $\neg {𝖣𝗂𝗌𝗍𝗂𝗇𝗀𝗎𝗂𝗌𝗁}_{i^{\ast }}$ occurs, it guesses an output bit uniformly and thus outputs $b^{\prime }=b$ with probability $1/2$. Thus we have

$$\mathrm{Pr}[{ℛ}_{2\to 3}^{i^{\ast }}\mathrm{outputs}{b}^{\prime }=b]=\mathrm{Pr}[\neg {𝖣𝗂𝗌𝗍𝗂𝗇𝗀𝗎𝗂𝗌𝗁}_{i^{\ast }}]\cdot \frac{1}{2}+\mathrm{Pr}[{𝖣𝗂𝗌𝗍𝗂𝗇𝗀𝗎𝗂𝗌𝗁}_{i^{\ast }}\wedge \neg 𝖱𝖾𝖽𝗎𝖼𝖾]\cdot \frac{1}{2}+\mathrm{Pr}[{𝖣𝗂𝗌𝗍𝗂𝗇𝗀𝗎𝗂𝗌𝗁}_{i^{\ast }}\wedge 𝖱𝖾𝖽𝗎𝖼𝖾]$$

Recall that $e_{i^{\ast }}={\hat{e}}_b$ and it follows that

$$\mathrm{Pr}\left[𝖱𝖾𝖽𝗎𝖼𝖾|{𝖣𝗂𝗌𝗍𝗂𝗇𝗀𝗎𝗂𝗌𝗁}_{i^{\ast }}\right]=\mathrm{Pr}[(b=0\wedge f={\hat{e}}_1\wedge {\hat{e}}_1\ne {\hat{e}}_0)\vee (b=1\wedge f={\hat{e}}_0\wedge {\hat{e}}_0\ne {\hat{e}}_1)]=\frac{1}{|E_x|-1}\cdot \frac{|E_x|-1}{|E_x|}=\frac{1}{|E_x|}$$

and if we define $p_{i^{\ast }}(n)=\mathrm{Pr}\left[{𝖣𝗂𝗌𝗍𝗂𝗇𝗀𝗎𝗂𝗌𝗁}_{i^{\ast }}\right]$ then by combining the last two equations we get

$$\mathrm{Pr}[{ℛ}_{2\to 3}^{i^{\ast }}\mathrm{outputs}{b}^{\prime }=b]=\frac{1-p_{i^{\ast }}(n)}{2}+\frac{(|E_x|-1)\cdot p_{i^{\ast }}(n)}{2|E_x|}+\frac{p_{i^{\ast }}(n)}{|E_x|}=\frac{p_{i^{\ast }}(n)}{2|E_x|}+\frac{1}{2}$$

Next we will combine the reductions for the individual values of $i^{\ast }$ into a single reduction that also plays the hiding game for $C$. We start by defining

$$p(n)=\mathrm{Pr}[𝖣𝗂𝗌𝗍𝗂𝗇𝗀𝗎𝗂𝗌𝗁]=\mathrm{Pr}\left[\underset{i^{\ast }\in [r]}{\bigwedge }{𝖣𝗂𝗌𝗍𝗂𝗇𝗀𝗎𝗂𝗌𝗁}_{i^{\ast }}\right]=\mathrm{Pr}[\neg \underset{i^{\ast }\in [r]}{\bigvee }\neg {𝖣𝗂𝗌𝗍𝗂𝗇𝗀𝗎𝗂𝗌𝗁}_{i^{\ast }}]\le 1-\sum _{i^{\ast }\in [r]}(1-p_{i^{\ast }}(n))=1-r+\sum _{i^{\ast }\in [r]}{p}_{i^{\ast }}(n)$$

where the inequality follows from a union bound. The reduction $R_{2\to 3}$ samples $i^{\ast }\leftarrow [r]$ uniformly and outputs what ${ℛ}_{2\to 3}^{i^{\ast }}$ does. We have

$$\mathrm{Pr}[{ℛ}_{2\to 3}\mathrm{outputs}{b}^{\prime }=b]=\sum _{i^{\ast }\in [r]}\mathrm{Pr}[{ℛ}_{2\to 3}^{i^{\ast }}\mathrm{outputs}{b}^{\prime }=b]\cdot \frac{1}{r}=\frac{1}{2}+\sum _{i^{\ast }\in [r]}\frac{p_{i^{\ast }}(n)}{2|E_x|\cdot r}\ge \frac{1}{2}+\frac{p(n)+r-1}{2|E_x|\cdot r}$$

Finally, by the security of $C$ there must exist a negligible function $\epsilon$ such that $|\mathrm{Pr}[{ℛ}_{2\to 3}\mathrm{outputs}{b}^{\prime }=b]-1/2|\le \epsilon (n)$. This implies that

$$\epsilon (n)\ge \left|\frac{p(n)+r-1}{2|E_x|\cdot r}\right|\ge \frac{p(n)}{2|E_x|\cdot r}$$

and since $|E_x|$ and $r=|E_x|\cdot n$ are both upper-bounded by a polynomial in $n$, it follows that $\mathrm{Pr}[𝖣𝗂𝗌𝗍𝗂𝗇𝗀𝗎𝗂𝗌𝗁]=p(n)\le 2|E_x{|}^2\cdot n\cdot \epsilon (n)$ is negligible in $n$. Since $(𝒜,𝒵)$ have no advantage in distinguishing ${\text{Hʏʙʀɪᴅ}}_2$ from the ideal-world experiment when the event $\neg 𝖣𝗂𝗌𝗍𝗂𝗇𝗀𝗎𝗂𝗌𝗁$ occurs, we can conclude that

$${\left\{{\text{Hʏʙʀɪᴅ}}_2(n)\right\}}_{n\in \mathbb{N}}{\approx }_{𝖼}{\left\{{\text{Iᴅᴇᴀʟ}}_{{ℱ}_{𝖹𝖪}^{R_n},{𝒮}_{𝖯},𝒵}(n)\right\}}_{n\in \mathbb{N}}$$

and Lemma 1 follows by the transitivity of computational indistinguishability.$■$

---

Lemma 2: If $\mathrm{\Sigma }$ is an SHVZK sigma protocol for language $L$ with witness-relation $R$, such that the size of the challenge space $E_x$ is always at most polynomial in $|x|$, and if $C$ is a trapdoor straight-line extractable commitment scheme, then for every malicious PPT adversary $𝒜$ that statically corrupts the verifier, there exists a PPT straight-line simulator ${𝒮}_{𝖵}$ such that for every PPT environment $𝒵$,

$${\left\{{\text{Rᴇᴀʟ}}_{{\pi }_{𝖹𝖪}^{{\mathrm{\Sigma }}_n,C},𝒜,𝒵}(n)\right\}}_{n\in \mathbb{N}}{\approx }_{𝖼}{\left\{{\text{Iᴅᴇᴀʟ}}_{{ℱ}_{𝖹𝖪}^{R_n},{𝒮}_{𝖵},𝒵}(n)\right\}}_{n\in \mathbb{N}}$$

Proof: We will begin by describing the simulator, and then we will argue for the indistinguishability of the real and ideal experiments via a sequence of hybrid experiments.

First Hybrid Experiment and Reduction. Now consider a hybrid experiment ${\text{Hʏʙʀɪᴅ}}_1$ which is exactly like the real-world experiment, except that in Step 2, ${ℱ}_{𝖢𝖱𝖲}$ uses $C.𝖳𝖦𝖾𝗇$ to sample $k_{𝖵}$ instead of $C.𝖦𝖾𝗇$. By a simple reduction to the trapdoor-indistinguishability property of $C$, we can show that

$${\left\{{\text{Rᴇᴀʟ}}_{{\pi }_{𝖹𝖪}^{{\mathrm{\Sigma }}_n,C},𝒜,𝒵}(n)\right\}}_{n\in \mathbb{N}}{\approx }_{𝖼}{\left\{{\text{Hʏʙʀɪᴅ}}_1(n)\right\}}_{n\in \mathbb{N}}$$

Second Hybrid Experiment and Reduction. Consider a second hybrid experiment ${\text{Hʏʙʀɪᴅ}}_2$, which is exactly like ${\text{Hʏʙʀɪᴅ}}_1$ except that the experiment checks whether $C.{𝖤𝗑𝗍}_t(c_{𝖵})\ne C.{𝖮𝗉𝖾𝗇}_{k_{𝖵}}(c_{𝖵},d_{𝖵})$, and behaves as though the opening $d_{𝖵}$ is invalid if so. Suppose there is a pair $(𝒜,𝒵)$ that can distinguish ${\text{Hʏʙʀɪᴅ}}_2$ from ${\text{Hʏʙʀɪᴅ}}_1$; they can do so only by contriving to cause $C.{𝖤𝗑𝗍}_t(c_{𝖵})\ne C.{𝖮𝗉𝖾𝗇}_{k_{𝖵}}(c_{𝖵},d_{𝖵})\ne \perp$. We will prove that this event happens with negligible probability via a reduction to the straight-line extractability property of $C$.

The reduction ${ℛ}_{1\to 2}$ plays the straight-line extractability game for $C$ and emulates ${\text{Hʏʙʀɪᴅ}}_1(n)$ internally toward $(𝒜,𝒵)$. In the emulated experiment, ${ℛ}_{1\to 2}$ emits its own challenge key $k$ as $k_{𝖵}$ on behalf of ${ℱ}_{𝖢𝖱𝖲}$ in Step 2, and it halts the experiment upon receiving $(c_{𝖵},d_{𝖵})$ in Step 6. Note that at this point, the emulated experiment is identically distributed to both ${\text{Hʏʙʀɪᴅ}}_2$ and ${\text{Hʏʙʀɪᴅ}}_1$. ${ℛ}_{1\to 2}$ outputs $(c_{𝖵},d_{𝖵})$ to the straight-line-extractability game for $C$, and wins the game precisely when $(𝒜,𝒵)$ cause the distinguishing condition to occur. By the security of $C$ there exists a negligible function $\epsilon$ that upper-bounds the reduction's probability of a win, which implies that for every PPT $(𝒜,𝒵)$,

$$\mathrm{Pr}[C.{𝖤𝗑𝗍}_t(c_{𝖵})\ne C.{𝖮𝗉𝖾𝗇}_{k_{𝖵}}(c_{𝖵},d_{𝖵})\ne \perp ]\le \epsilon (n)$$

and it follows that ${\left\{{\text{Hʏʙʀɪᴅ}}_1(n)\right\}}_{n\in \mathbb{N}}{\approx }_{𝖼}{\left\{{\text{Hʏʙʀɪᴅ}}_2(n)\right\}}_{n\in \mathbb{N}}$.

Third Reduction, over a Sequence of Hybrid Experiments. Next, we introduce a sequence of experiments ${\text{Hʏʙʀɪᴅ}}_{3,h,f}$ for $h\in [r]$ and $f\in E_x$, where the latter set is ordered in an arbitrary but deterministic way, which implies a fixed ordering for the experiments, and where $f_{|E_x|}$ denotes the maximal element of $E_x$. Each ${\text{Hʏʙʀɪᴅ}}_{3,h,f}$ is like the previous experiment in the sequence, except that if $C.{𝖤𝗑𝗍}_t(c_{𝖵})\ne \perp$ and $e_h=f$, then ${\text{Hʏʙʀɪᴅ}}_{3,h,f}$ samples $(a_h,z_{h,f})\leftarrow {\mathrm{\Sigma }}_n.𝖲𝗂𝗆(x,f)$ rather than $(a_h,u_h)\leftarrow {\mathrm{\Sigma }}_n.𝖥𝗂𝗋𝗌𝗍(x,w)$ and $z_{h,f}\leftarrow {\mathrm{\Sigma }}_n.𝖳𝗁𝗂𝗋𝖽(x,w,u_h,f)$. By the hybrid lemma [PS10, Lemma 71.6] (see also [Goldreich04, Section 3.2.3]), we know that if there is a pair $(𝒜,𝒵)$ that can distinguish ${\text{Hʏʙʀɪᴅ}}_2(n)$ from ${\text{Hʏʙʀɪᴅ}}_{3,r,f_{|E_x|}}(n)$ with advantage $\delta (n)$, then we can write a simple reduction that plays the SHVZK game for $\mathrm{\Sigma }$ and achieves advantage $\delta (n)/(|E_x|\cdot r)$.

Specifically, the reduction ${ℛ}_{2\to 3}$ samples $h^{\ast }\leftarrow [r]$ and $f^{\ast }\leftarrow E_x$ uniformly, and it emulates the experiment ${\text{Hʏʙʀɪᴅ}}_{3,h^{\ast },f^{\ast }}$ internally toward $(𝒜,𝒵)$, except that if $e_{h^{\ast }}=f^{\ast }$, then the reduction outputs $(x,w,e_{h^{\ast }})$ to the challenger in the SHVZK game and receives $(a_{h^{\ast }},z_{h^{\ast },f^{\ast }})$ in response, which it embeds the the emulated experiment in the appropriate way. The reduction runs the emulated experiment to completion and outputs whatever the internally-emulated $𝒵$ does. Note that if $b=1$ in the SHVZK game, then the experiment emulated within ${ℛ}_{2\to 3}$ is distributed identically to ${\text{Hʏʙʀɪᴅ}}_{3,h^{\ast },f^{\ast }}$; otherwise it is distributed identically to the previous hybrid in the sequence. Thus the advantage of ${ℛ}_{2\to 3}$ is equal to the expected advantage of $(𝒜,𝒵)$ over the choice of $h^{\ast }$ and $f^{\ast }$.

If we let ${\delta }_{h,f}(n)$ be the advantage of $(𝒜,𝒵)$ in distinguishing ${\text{Hʏʙʀɪᴅ}}_{3,h,f}(n)$ from the previous experiment in the sequence, then by the triangle inequality,

$$\sum _{h\in [r],f\in E_x}{\delta }_{h,f}(n)\ge \delta (n)$$

which implies that the total advantage of ${ℛ}_{2\to 3}$ is

$$\sum _{h\in [r],f\in E_x}\frac{{\delta }_{h,f}}{|E_x|\cdot r}(n)\ge \delta (n)/(|E_x|\cdot r)$$

By the security of $\mathrm{\Sigma }$, there exists a negligible function $\epsilon$ that upper-bounds the advantage of ${ℛ}_{2\to 3}$, and since $|E_x|$ and $r=|E_x|\cdot n$ are both upper-bounded by a polynomial in $n$, it follows that $\delta (n)\le |E_x|\cdot r\cdot \epsilon (n)$ is negligible for every $(𝒜,𝒵)$, and thus

$${\left\{{\text{Hʏʙʀɪᴅ}}_2(n)\right\}}_{n\in \mathbb{N}}{\approx }_{𝖼}{\left\{{\text{Hʏʙʀɪᴅ}}_{3,r,f_{|E_x|}}(n)\right\}}_{n\in \mathbb{N}}$$

Fourth Reduction, over a Sequence of Hybrid Experiments. We introduce a second sequence of experiments ${\text{Hʏʙʀɪᴅ}}_{4,h,f}$ for $h\in [r]$ and $f\in E_x$, with the latter set ordered as above. Each ${\text{Hʏʙʀɪᴅ}}_{4,h,f}$ is like the previous experiment in the sequence, except that if $C.{𝖤𝗑𝗍}_t(c_{𝖵})=\perp$ or $e_h\ne f$, then ${\text{Hʏʙʀɪᴅ}}_{4,h,f}$ sets $z_{h,f}:=0$ rather than $z_{h,f}\leftarrow {\mathrm{\Sigma }}_n.𝖳𝗁𝗂𝗋𝖽(x,w,u_h,f)$. Note that in the case that this change has an effect on the hybrid's distribution, the commitment $c_{h,f}$ will never be opened. Again by the hybrid lemma, we know that if there is a pair $(𝒜,𝒵)$ that can distinguish ${\text{Hʏʙʀɪᴅ}}_{3,r,f_{|E_x|}}(n)$ from ${\text{Hʏʙʀɪᴅ}}_{4,r,f_{|E_x|}}(n)$ with advantage $\delta (n)$, then we can write a simple reduction that plays the hiding game for $C$ and achieves advantage $\delta (n)/(|E_x|\cdot r)$. This reduction works exactly like ${ℛ}_{2\to 3}$, except that it plays the commitment hiding game instead of the SHVZK game, and it emits its own challenge key $k$ as $k_{𝖯}$ on behalf of ${ℱ}_{𝖢𝖱𝖲}$ in Step 1. By the security of $\mathrm{C}$, there exists a negligible function $\epsilon$ that upper-bounds the advantage of this reduction, and since $|E_x|$ and $r=|E_x|\cdot n$ are both upper-bounded by a polynomial in $n$, it follows that $\delta (n)\le |E_x|\cdot r\cdot \epsilon (n)$ is negligible for every $(𝒜,𝒵)$, and thus

$${\left\{{\text{Hʏʙʀɪᴅ}}_{3,r,f_{|E_x|}}(n)\right\}}_{n\in \mathbb{N}}{\approx }_{𝖼}{\left\{{\text{Hʏʙʀɪᴅ}}_{4,r,f_{|E_x|}}(n)\right\}}_{n\in \mathbb{N}}$$

Fifth Reduction, over a Sequence Ending in the Ideal World. There remains only one event in which the distribution of ${\text{Hʏʙʀɪᴅ}}_{4,r,f_{|E_x|}}$ differs from that of the ideal-world experiment: if $C.{𝖤𝗑𝗍}_t(c_{𝖵})=\perp$, then the ideal-world experiment uses $(a_i,z_i^{\prime })\leftarrow {\mathrm{\Sigma }}_n.𝖲𝗂𝗆(x,e^{\prime })$ (where $e^{\prime }\in E_x$ is an arbitrary, fixed value) to sample $a_i$ for every $i\in [r]$, whereas ${\text{Hʏʙʀɪᴅ}}_{4,r,f_{|E_x|}}$ uses $(a_i,u_i)\leftarrow {\mathrm{\Sigma }}_n.𝖥𝗂𝗋𝗌𝗍(x,w)$. Note that in both experiments, the corresponding response $z_{i,e^{\prime }}$ is set to $0$ in this event, and it is committed but never revealed.

We introduce a final sequence of hybrid experiments ${\text{Hʏʙʀɪᴅ}}_{5,h}$ for $h\in [r]$, each of which is like the previous experiment in the sequence except that if $C.{𝖤𝗑𝗍}_t(c_{𝖵})=\perp$, then ${\text{Hʏʙʀɪᴅ}}_{5,h}$ uses $(a_h,z_h^{\prime })\leftarrow {\mathrm{\Sigma }}_n.𝖲𝗂𝗆(x,e^{\prime })$ to sample $a_h$ rather than $(a_h,u_h)\leftarrow {\mathrm{\Sigma }}_n.𝖥𝗂𝗋𝗌𝗍(x,w)$. Again by the hybrid lemma, we know that if there is a pair $(𝒜,𝒵)$ that can distinguish ${\text{Hʏʙʀɪᴅ}}_{4,r,f_{|E_x|}}(n)$ from ${\text{Hʏʙʀɪᴅ}}_{5,r}(n)$ with advantage $\delta (n)$, then we can write a simple reduction that plays the SHVZK game for $\mathrm{\Sigma }$ and achieves advantage $\delta (n)/r$. This reduction is similar to ${ℛ}_{2\to 3}$, but it has the value $e^{\prime }$ hardcoded rather than guessing $f^{\ast }\in E_x$, and it does not need to use $z_{h^{\ast }}^{\prime }$ anywhere. By the security of $\mathrm{\Sigma }$, there exists a negligible function $\epsilon$ that upper-bounds the advantage of this reduction, and since $r=|E_x|\cdot n$ is upper-bounded by a polynomial in $n$, it follows that $\delta (n)\le r\cdot \epsilon (n)$ is negligible for every $(𝒜,𝒵)$, and thus

$${\left\{{\text{Hʏʙʀɪᴅ}}_{4,r,f_{|E_x|}}(n)\right\}}_{n\in \mathbb{N}}{\approx }_{𝖼}{\left\{{\text{Hʏʙʀɪᴅ}}_{5,r}(n)\right\}}_{n\in \mathbb{N}}$$

It remains to observe that ${\text{Hʏʙʀɪᴅ}}_{5,r}$ does not make use of the prover's witness $w$ in any way, and it is distributed identically to the ideal-world experiment from the perspective of the environment. Thus Lemma 2 follows by the transitivity of computational indistinguishability.$■$