Protocol Description


We take as our security parameter, and unless explicitly noted all algorithms and adversaries are probabilistic (interactive) Turing machines that run in polynomial time in this security parameter. We use to denote a function that is negligible in .

Cryptographic Groups

We let denote a cyclic group of prime order . The identity of a group is written as . We refer to the scalars of elements in as elements in a scalar field of size . Group elements are written in capital letters while scalars are written in lowercase or Greek letters. Vectors of scalars or group elements are written in boldface, i.e. and . Group operations are written additively and the multiplication of a group element by a scalar is written .

We will often use the notation to describe the inner product of two like-length vectors of scalars . We also use this notation to represent the linear combination of group elements such as with , computed in practice by a multiscalar multiplication.

We use to describe a vector of length that contains only zeroes in .

Discrete Log Relation Problem. The advantage metric is defined with respect the following game.

Given an -length vector of group elements, the discrete log relation problem asks for such that and yet , which we refer to as a non-trivial discrete log relation. The hardness of this problem is tightly implied by the hardness of the discrete log problem in the group as shown in Lemma 3 of [JT20]. Formally, we use the game defined above to capture this problem.

Interactive Proofs

Interactive proofs are a triple of algorithms . The algorithm produces as its output some public parameters commonly refered to by . The prover and verifier are interactive machines (with access to ) and we denote by an algorithm that executes a two-party protocol between them on inputs . The output of this protocol, a transcript of their interaction, contains all of the messages sent between and . At the end of the protocol, the verifier outputs a decision bit.

Zero knowledge Arguments of Knowledge

Proofs of knowledge are interactive proofs where the prover aims to convince the verifier that they know a witness such that for a statement and polynomial-time decidable relation . We will work with arguments of knowledge which assume computationally-bounded provers.

We will analyze arguments of knowledge through the lens of four security notions.

  • Completeness: If the prover possesses a valid witness, can they always convince the verifier? It is useful to understand this property as it can have implications for the other security notions.
  • Soundness: Can a cheating prover falsely convince the verifier of the correctness of a statement that is not actually correct? We refer to the probability that a cheating prover can falsely convince the verifier as the soundness error.
  • Knowledge soundness: When the verifier is convinced the statement is correct, does the prover actually possess ("know") a valid witness? We refer to the probability that a cheating prover falsely convinces the verifier of this knowledge as the knowledge error.
  • Zero knowledge: Does the prover learn anything besides that which can be inferred from the correctness of the statement and the prover's knowledge of a valid witness?

First, we will visit the simple definition of completeness.

Perfect Completeness. An interactive argument has perfect completeness if for all polynomial-time decidable relations and for all non-uniform polynomial-time adversaries


Complicating our analysis is that although our protocol is described as an interactive argument, it is realized in practice as a non-interactive argument through the use of the Fiat-Shamir transformation.

Public coin. We say that an interactive argument is public coin when all of the messages sent by the verifier are each sampled with fresh randomness.

Fiat-Shamir transformation. In this transformation an interactive, public coin argument can be made non-interactive in the random oracle model by replacing the verifier algorithm with a cryptographically strong hash function that produces sufficiently random looking output.

This transformation means that in the concrete protocol a cheating prover can easily "rewind" the verifier by forking the transcript and sending new messages to the verifier. Studying the concrete security of our construction after applying this transformation is important. Fortunately, we are able to follow a framework of analysis by Ghoshal and Tessaro ([GT20]) that has been applied to constructions similar to ours.

We will study our protocol through the notion of state-restoration soundness. In this model the (cheating) prover is allowed to rewind the verifier to any previous state it was in. The prover wins if they are able to produce an accepting transcript.

State-Restoration Soundness. Let be an interactive argument with verifier challenges and let the th challenge be sampled from . The advantage metric of a state restoration prover is defined with respect to the following game.

As shown in [GT20] (Theorem 1) state restoration soundness is tightly related to soundness after applying the Fiat-Shamir transformation.

Knowledge Soundness

We will show that our protocol satisfies a strengthened notion of knowledge soundness known as witness extended emulation. Informally, this notion states that for any successful prover algorithm there exists an efficient emulator that can extract a witness from it by rewinding it and supplying it with fresh randomness.

However, we must slightly adjust our definition of witness extended emulation to account for the fact that our provers are state restoration provers and can rewind the verifier. Further, to avoid the need for rewinding the state restoration prover during witness extraction we study our protocol in the algebraic group model.

Algebraic Group Model (AGM). An adversary is said to be algebraic if whenever it outputs a group element it also outputs a representation such that where is the vector of group elements that has seen so far. Notationally, we write to describe a group element enhanced with this representation. We also write to identify the component of the representation of that corresponds with . In other words,

The algebraic group model allows us to perform so-called "online" extraction for some protocols: the extractor can obtain the witness from the representations themselves for a single (accepting) transcript.

State Restoration Witness Extended Emulation Let be an interactive argument for relation with challenges. We define for all non-uniform algebraic provers , extractors , and computationally unbounded distinguishers the advantage metric is defined with the respect to the following games.

Zero Knowledge

We say that an argument of knowledge is zero knowledge if the verifier also does not learn anything from their interaction besides that which can be learned from the existence of a valid . More formally,

Perfect Special Honest-Verifier Zero Knowledge. A public coin interactive argument has perfect special honest-verifier zero knowledge (PSHVZK) if for all polynomial-time decidable relations and for all and for all non-uniform polynomial-time adversaries there exists a probabilistic polynomial-time simulator such that where is the internal randomness of the verifier.

In this (common) definition of zero-knowledge the verifier is expected to act "honestly" and send challenges that correspond only with their internal randomness; they cannot adaptively respond to the prover based on the prover's messages. We use a strengthened form of this definition that forces the simulator to output a transcript with the same (adversarially provided) challenges that the verifier algorithm sends to the prover.


Let be a primitive root of unity forming the domain with the vanishing polynomial over this domain. Let be positive integers. We present an interactive argument for the relation where are (multivariate) polynomials with degree in and has degree in .

returns .

For all :

  • Let be the exhaustive set of integers (modulo ) such that appears as a term in .
  • Let be a list of distinct sets of integers containing and the set .
  • Let when .

Let denote the size of , and let denote the size of every without loss of generality.

In the following protocol, we take it for granted that each polynomial is defined such that blinding factors are freshly sampled by the prover and are each present as an evaluation of over the domain .

  1. and proceed in the following rounds of interaction, where in round (starting at )
  • sets
  • sends a hiding commitment where are the coefficients of the univariate polynomial and is some random, independently sampled blinding factor elided for exposition.
  • responds with a challenge .
  1. and set .
  2. sends a commitment where are the coefficients of a randomly sampled univariate polynomial of degree .
  3. computes univariate polynomial of degree .
  4. computes at most degree polynomials such that .
  5. sends commitments for all where denotes the vector of coefficients for .
  6. responds with challenge and computes .
  7. sets .
  8. sends and for all sends such that for all .
  9. For all and set to be the lowest degree univariate polynomial defined such that for all .
  10. responds with challenges and initializes .
  • Starting at and ending at sets .
  • finally sets .
  1. initializes .
  • Starting at and ending at sets .
  • finally sets .
  1. and initialize .
  • Starting at and ending at and set .
  • Finally and set and where is computed by as using the values provided by .
  1. sends where defines the coefficients of the polynomial
  2. responds with challenge .
  3. sends such that for all .
  4. responds with challenge .
  5. and set and
  6. sets .
  7. samples a random polynomial of degree with a root at and sends a commitment where defines the coefficients of .
  8. responds with challenges .
  9. and set .
  10. sets .
  11. Initialize as the coefficients of and and . and will interact in the following rounds, where in the th round starting in round and ending in round :
  • sends and .
  • responds with challenge .
  • and set and .
  • sets .
  1. sends and synthetic blinding factor .
  2. accepts only if .