2022-08-21

The Paper that Keeps Showing Up

Let's talk about one of my favorite cryptography papers.

This is the paper that keeps showing up. It's almost comical at this point. It's shown up 5 times in my last semester at EPFL, across 3 different courses. It showed up as part of the paper my colleague and I reviewed for a seminar, it showed up for attribute-based credentials in a course about Privacy-Enhancing-Technologies, it showed up in an advanced Cryptography course on two homeworks, and on the final exam!

Everywhere I go, I see this paper, and no one even seems to be aware of the fact that they're using it!

What is this wonderful gem, you might ask?

Well, it's none other than "Unifying Zero-Knowledge Proofs of Knowledge", by Ueli Maurer ¹:

This paper is short, but contains a very interesting result. Maurer taks the humble Schnorr signature / proof, which lets you prove knowledge of a scalar $x$ such that $x \cdot G = X$ , without revealing that scalar, and generalizes this scheme to work for any group homomorphism!

[!note] Note: This is a function $\varphi$ such that:
$\varphi(a + b) = \varphi(a) + \varphi(b)$

This captures a very wide swathe of functionality, from Schnorr signatures, to Pedersen commitments, to attribute-based credentials, to polynomial commitment schemes. We'll be seeing how to construct all of these examples, and more, in the rest of this post, so let's dive right into it!

Warmup: Schnorr Proofs

As a bit of a warmup, let's go over how Schnorr proofs work. These are also a great example to introduce the relevant security notions we'll be working with, like completeness, soundness, etc.

We'll be working with a cryptographic group $\mathbb{G}$ , generated by $G$ , of prime order $q$ , and with an associated field of scalars $\mathbb{F}_q$ .

In a Schnorr proof, the prover has a secret $x \in \mathbb{F}_q$ , and a public value $X \in \mathbb{G}$ . The prover wants to demonstrate that $X = x \cdot G$ , without revealing $x$ .

For the prover to convince the verifier, the two of them run a protocol together:

\boxed{ \begin{aligned} &\mathcal{P} \text{ knows } x \in \mathbb{F}_q&\quad&\mathcal{V} \text{ knows } X \in \mathbb{G} \cr \cr &k \xleftarrow{R} \mathbb{F}_q\cr &K \gets k \cdot G\cr &&\xrightarrow{K}\cr &&&c \xleftarrow{R} \mathbb{F}_q\cr &&\xleftarrow{c}\cr &s \gets k + c \cdot x\cr &&\xrightarrow{s}\cr &&&s \cdot G \stackrel{?}{=} K + c \cdot X\cr \end{aligned} }

The prover generates their random nonce $k$ , and then sends $K := k \cdot G$ , which is, in essence, a commitment to this nonce. The verifier responds in turn with a random challenge $c$ , which the prover then uses to create their response $s$ . Finally, the verifier checks that the response is consistent with the challenge and the public input $X$ .

Completeness

The first property we want a protocol like this to satisfy is completeness. If $x$ is correct, i.e. $X = x \cdot G$ , then we need verification to succeed at the end of the protocol, assuming that the prover behaves honestly.

To see why this is the case, we need to use the linearity of scalar multiplication:

(a + b) \cdot G = a \cdot G + b \cdot G

If we apply this to the response $s$ , we get:

s \cdot G = (k + c \cdot x) \cdot G = k \cdot G+ c \cdot (x \cdot G) = K + c \cdot X

And so, the verification check will pass.

It's crucial here that $s$ is actually equal to $k + c \cdot x$ , and that $X = x \cdot G$ , which requires the prover to be honest. Completeness just says that if the prover is honest, and that the property they're trying to prove holds, then the protocol will succeed. Completeness doesn't say anything about the case where the prover misbehaves, or where the property doesn't actually hold.

Honest Verifier Zero-Knowledge

One way to demonstrate knowledge of a value $x$ such that $x \cdot G = X$ would be to simply reveal the value $x$ . The reason we do this complicated Schnorr protocol instead is because we want to prove that we know such an $x$ without revealing it. In fact, we don't want to reveal any information about $x$ whatsoever.

This is where the honest verifier zero-knowledge property comes in. In essence, it says that if the verifier behaves honestly, then they don't learn any information about the secret value $x$ . At least, not any information that they couldn't have gotten just by knowing the public value $X$ .

Capturing the notion of "not learning any information" is tricky. To do this, we use a simulator $\mathcal{S}$ . This simulator $\mathcal{S}$ takes as input the public input $X$ , and the challenge $c$ , and then creates values $K$ and $s$ which should have the same distribution of the actual messages sent by the prover in the real protocol.

The intuition here is that because the verifier can't distinguish between the messages from a real protocol, and the messages created by the simulator, then they learn nothing that they didn't know before, since they already had access to both $X$ and $c$ . It's important that the verifier behave honestly, and choose their challenge $c$ at random, and not change the way they choose $c$ based on $K$ . Because this challenge $c$ is independent from $K$ , you could generate it before even seeing $K$ , which means that the messages that you see after that, including $K$ , could be coming from a simulator instead, without the verifier realizing it. On the other hand, if the verifier misbehaves, and chooses $c$ differently depending on $K$ , then our simulation strategy has to work a bit differently.

In this case, the simulator is pretty simple. We know that the commitment $K$ and response $s$ must satisfy:

s \cdot G = K + c \cdot X

Our simulator $\mathcal{S}$ needs to return $(K, s)$ as a function of $(X, c)$ . One way to do this is to simply choose $s$ at random, and then set:

K \gets s \cdot G - c \cdot X

Because $s$ is random, the value $K$ ends up also being a random group element, which is the same as for a real execution of the protocol. Ditto with $s$ itself.

This is enough to show that the Schnorr protocol is honest verifier zero-knowledge.

2-Extractability

At this point, we know that if the prover is honest, then they convince the verifier. We also know that an honest verifier learns nothing by running the protocol. But what if the prover is dishonest?

We don't want the prover to be able to convince the verifier unless they actually know an $x$ such that $x \cdot G = X$ .

Our strategy to show this will be to use an extractor. The idea is that if we have two transcripts $(K, c, s)$ and $(K, c', s')$ , with $c \neq c'$ , which share the same first message, then our extractor $\mathcal{E}$ will be able to produce a value $\hat{x}$ satisfying ${\hat{x} \cdot G = X}$ .

This means that the prover must have known such a value.

The intuition here is that you treat the prover as a machine with the value embedded inside of it, somehow. Then, you can get these two transcripts by rewinding this machine. After sending the first challenge $c$ and getting the response $s$ , you rewind the machine back to the point where it sent $K$ , and now you send it a new challenge $c'$ , and get a new response $s'$ .

Intuitively, if the value $x$ is embedded inside of the machine, then rewinding doesn't change this fact. If we can successfully extract the value using these two forked transcripts, that means the value was always present inside of the machine.

Here's another analogy. Let's say we had access to a time machine. We could use this time machine to wind back time to when the prover sent $K$ , and use that to get our two transcripts. Now, having a time machine doesn't change whether or not a value was embedded inside of the prover, so this convinces us that they knew this value to begin with.

Note that this rewinding is really more of a theoretical point, which we use in proving the soundness of the protocol. We don't actually need to be able to rewind the protocol. This rewinding might be problematic for concurrent security, but that's a can of worms best left unopened for now.

With that aside, let's actually create this extractor, shall we?

Given our two transcripts $(K, c, s)$ and $(K, c', s')$ we know that they must satisfy:

\begin{aligned} &s \cdot G = K + c \cdot X\cr &s' \cdot G = K + c' \cdot X\cr \end{aligned}

If we subtract the two equations, we get:

(s - s') \cdot G = (c - c') \cdot X

Finally, since $c \neq c'$ , we can divide by $(c - c')$ to get:

\frac{(s - s')}{(c - c')} \cdot G = X

We now see that if our extractor sets:

\hat{x} \gets (s - s') / (c - c')

then they've managed to find a value $\hat{x}$ such that $\hat{x} \cdot G = X$ , as promised.

Aside: Sigma Protocols

This Schnorr protocol is a specific example of what we call a sigma protocol.

This is a three move protocol, wherein the prover sends a commitment, the verifier samples a random public challenge, the prover sends a response, and then a verification check based on the transcript and the public input is run.

The Maurer proofs we'll see in the next section are also sigma protocols.

Because the verifier's challenge is completely public, and the verification check doesn't depend on any internal state in the verifier, we call this a public coin protocol.

What's nice about public coin protocols is that they can be made non-interactive, via the Fiat-Shamir transform. The idea is that instead of having a verifier choose a challenge, we instead emulate this choice with a hash function $H$ , whose output should function in the same way as the random challenge.

This allows the prover to create a proof without interacting with anybody else, and this proof can be independently verified by different people.

Schnorr signatures are really just the application of this transform to the protocol we saw earlier, with the inclusion of the message we want to sign, $m$ , inside of the hash function, so that the proof is "bound" to this specific message.

Generalization: Maurer Proofs

Maurer proofs ¹ can be seen as a vast generalization of Schnorr proofs.

Given a group homomorphism $\varphi : \mathbb{A} \to \mathbb{B}$ , they allow you to prove knowledge of $a \in \mathbb{A}$ such that $\varphi(a) = B$ , without revealing the secret $a$ . Specifically, you don't learn anything more about $a$ than you could have learned from $B$ .

[!note] Note: Given two groups $\mathbb{A}$ and $\mathbb{B}$ , a homomorphism $\varphi$ is a function from $\mathbb{A}$ to $\mathbb{B}$ such that for all $a, a' \in \mathbb{A}$ , we have:
$\varphi(a + a') = \varphi(a) + \varphi(a')$

Schnorr proofs are a specific case of these proofs, with the homomorphism:

\begin{aligned} \psi &: (\mathbb{F}_q, +) \to \mathbb{G}\cr \psi(x) &:= x \cdot G\cr \end{aligned}

The protocol for the general case of $\varphi : \mathbb{A} \to \mathbb{B}$ is very similar to Schnorr proofs as well:

\boxed{ \begin{aligned} &\mathcal{P} \text{ knows } a \in \mathbb{A}&\quad&\mathcal{V} \text{ knows } B \in \mathbb{B} \cr \cr &k \xleftarrow{R} \mathbb{A}\cr &K \gets \varphi(k)\cr &&\xrightarrow{K}\cr &&&c \xleftarrow{R} \mathcal{C}\cr &&\xleftarrow{c}\cr &s \gets k + c \cdot a\cr &&\xrightarrow{s}\cr &&&\varphi(s) \stackrel{?}{=} K + c \cdot B\cr \end{aligned} }

The protocol proceeds in a familar way. The prover generates a random nonce $k$ , sends their commitment $\varphi(k)$ , the verifier responds with a challenge $c$ , and the prover concludes with their response $s$ .

The set $\mathcal{C}$ denotes the challenge space. The way we define this set depends on the homomorphism $\varphi$ , and the public value $B$ . We'll see what conditions we need this set to satisfy when we prove extraction for this protocol.

Completeness

Completeness holds because $\varphi$ is a homomorphism:

\varphi(s) = \varphi(k + c \cdot a) = \varphi(k) + c \cdot \varphi(a) = K + c \cdot B

Honest Verifier Zero-Knowledge

The simulator is also pretty simple to define.

Given a challenge $c$ , we know that $K$ and $s$ must satisfy:

\varphi(s) = K + c \cdot B

The idea behind our simulator, like with Schnorr proofs, is to generate a random $s$ , and then define $K$ as a function of $s$ , $B$ , and $c$ :

K \gets \varphi(s) - c \cdot B

Since $s$ is random, this makes $K$ as random as in the real protocol, and so our simulator works.

Extraction

Extraction is a bit trickier, because we need to choose our challenge space $\mathcal{C}$ . This is simple when we know the order of the group $\mathbb{B}$ , but we can also find challenge spaces which work even if the order of the group is unknown.

Our extractor has access to two transcripts $(K, c, s)$ and $(K, c', s')$ , with $c \neq c'$ . These transcripts are valid, and so satisfy:

\begin{aligned} \varphi(s) &= K + c \cdot B\cr \varphi(s') &= K + c' \cdot B\cr \end{aligned}

If we subtract the equations, we get:

\varphi(s) - \varphi(s') = (c - c') \cdot B

Since $\varphi(s)$ is a homomorphism, we can write:

\varphi(s - s') = (c - c') \cdot B

Now, if we knew the order of $\mathbb{B}$ , say $q$ , then we could invert $c - c'$ mod $q$ , giving us:

\frac{1}{(c - c')} \cdot \varphi(s - s') = B

and then use the fact that $\varphi(s - s')$ is a homomorphism, giving us:

\varphi \left(\frac{s - s'}{c - c'}\right) = B

And we could then use this value as our extractor.

But it turns out that you can make the extraction work even if you don't know the order.

To do this, we need to assume the existence of an "anchor value" $u \in \mathbb{A}$ , such that there exists $l$ with:

\varphi(u) = l \cdot B

We also require that $\gcd(l, (c - c')) = 1$ for all $c \neq c' \in \mathcal{C}$ . This means that there exists coefficients $\alpha, \beta \in \mathbb{Z}$ such that:

\alpha \cdot l + \beta (c - c') = 1

We can then use this to define our extracted value $\hat{x}$ :

\hat{x} := \alpha \cdot u + \beta \cdot (s - s')

To see why this works, remember that $\varphi(s - s') = (c - c') \cdot B$ , which means that:

\begin{aligned} \varphi(\hat{x}) &=\cr \varphi(\alpha \cdot u + \beta \cdot (s - s')) &=\cr \alpha \cdot \varphi(u) + \beta \cdot \varphi(s - s') &=\cr \alpha \cdot l \cdot B + \beta \cdot (c - c') \cdot B &=\cr (\alpha \cdot l + \beta \cdot (c - c')) \cdot B &=\cr 1 \cdot B &= B\cr \end{aligned}

We also need the set $\mathcal{C}$ to be large enough, e.g. $|\mathcal{C}| \geq 2^\lambda$ , with $\lambda$ our security parameter. Or, we could use a smaller set, and do multiple repetitions of the protocol.

Examples of Extraction

In summary, we need a large set $\mathcal{C}$ such that for any $c \neq c' \in \mathcal{C}$ , there exists an anchor value $u$ and exponent $l$ such that:

\varphi(u) = l \cdot B

and $\gcd(l, c - c') = 1$ .

Let's see a few examples of how this works.

Extraction for Groups of Known Prime Order

If you know the order of a group $\mathbb{B}$ , and this group has prime order $q$ , then you can easily create this set.

The element $0 \in \mathbb{A}$ can act as our anchor value, since $q \cdot B = 0 = \varphi(0)$ , no matter what value $B$ has.

Furthermore, if we take $\mathcal{C} = \mathbb{F}_q$ , then the difference between any two elements in $\mathbb{F}_q$ will be coprime with $q$ , since $q$ is a prime number, and the difference will be ${< q}$ .

In fact, instead of using the order of the group, it suffices to use the exponent. This is a value $e$ such that $e \cdot B = 0$ for any value $B \in \mathbb{B}$ . When taking the product of several groups, this will be smaller than the order, which is nice.

Extraction for RSA

[!note] Note: In this section, and when mentioning RSA later, I will switch to the inferior multiplicative notation, because I fear that the world is not yet ready for additive notation RSA.

Let's say that you want to do this for an RSA group $(\mathbb{Z}/(N), \cdot)$ . The issue is that you don't know the order of this group.

The homomorphism in this case is:

\varphi(x) := x^e

(done modulo $N$ )

You also know a public value $y$ , claimed to equal $x^e$ for some secret $x$ .

This homomorphism naturally guides our choice of anchor. We need to find a $u$ such that $\varphi(u) = y^l$ . Unraveling $\varphi$ , we need $u^e = y^l$ .

Well, one simple way to satisfy this is to take $l = e$ and $u = y$ , giving us the equation:

y^e = y^e

Now, we need to find a set $\mathcal{C}$ where the difference with any two elements is coprime with $e$ . This is quite simple if $e$ is a prime number, which is usually the case: we can simply take $\mathcal{C} = \mathbb{Z}/(e)$ . All (non-negative) numbers $< e$ will have difference which is coprime with $e$ , since $e$ is prime.

Now, if $e$ is a small prime number, then we'll need to repeat our protocol several times for soundness. For example, if $e$ is $3$ , then we'd need to repeat our protocol $128 / (\text{lg } 3)$ times, for $128$ bit security.

Summary

In summary, given a group homomorphism $\varphi : \mathbb{A} \to \mathbb{B}$ , Maurer proofs are a sigma protocol for proving knowledge of a secret $a \in \mathbb{A}$ such that $\varphi(a) = B$ , for a public $B$ .

The only assumption we need to make about the groups is that we can construct a set $\mathcal{C}$ such that there exists an exponent $l \in \mathbb{Z}$ , with $\gcd(l, (c - c')) = 1$ for all $c \neq c' \in \mathcal{C}$ , and an anchor $u \in \mathbb{A}$ satisfying:

\varphi(u) = l \cdot B

Some Applications

We've now seen what Maurer proofs are, and how general they are. While they sure are neat, presented like this they may still be a bit uninteresting. When I first read the paper, I thought it was cool, but nothing to write home about. What really made it one of my favorite papers was accidentally stumbling into a bunch of applications that people weren't even aware were specific instances of Maurer proofs.

In this section, we'll be going over quite a few of these applications.

Schnorr Proofs

I've mentioned this one a few times already, but it's worth seeing again.

With a Schnorr proof, you want to show that you know a secret $x$ such that ${x \cdot G = X}$ , with $X$ public.

We can capture this with a convenient notation for relations:

\{(G, X ; x)\ |\ x \cdot G = X\}

The elements to the left of the $;$ are public, those to the right are private, and the statement after the $|$ is the relation which needs to hold.

We can write this as a Maurer relation:

\{(\varphi, X ; x)\ |\ \varphi(x) = X\}

With $\varphi(x) := x \cdot G$ , which is homomorphic.

The challenge set $\mathcal{C}$ can be chosen to be $\mathbb{F}_q$ , as explained earlier.

Guillou-Quisquater Proofs

The Guillou-Quisquater protocol ² is similar to Schnorr proofs, but instead works over an RSA group.

Given an RSA modulus $N$ , and public exponent $e$ (which we assume to be prime), you can define the following relation:

\{(N, e, y ; x) \ |\ x^e \equiv y \mod N \}

But, this is really just an instance of a Maurer relation, with the homomorphism:

\begin{aligned} &\varphi : (\mathbb{Z}/(N), \cdot) \to (\mathbb{Z}/(N), \cdot)\cr &\varphi(x) := x^e \mod N \end{aligned}

We also need to pick our challenge set $\mathcal{C}$ . If $e$ is a prime number, then we can simply take $\mathbb{Z}/(e)$ , as we saw earlier.

We might need several parallel repetitions of the protocol if $e$ is small though.

Parallel Schnorr

One useful extension of Schnorr proofs is when you want to prove multiple instances in parallel:

\{(G, A, B; a, b)\ |\ a \cdot G = A \land b \cdot G = B \}

Interestingly enough, this is also an instance of a Maurer relation, with the homomorphism:

\begin{aligned} &\varphi : \mathbb{F}^2_q \to \mathbb{G}^2\cr &\varphi(a, b) := (a \cdot G, b \cdot G) \end{aligned}

For our challenge set, we can simply use $\mathbb{F}_q$ , since $\text{lcm}(q, q) = q$ .

In general, taking products of group homomorphisms is an extremely useful way to create Maurer relations.

Pedersen Commitment Proofs

A Pedersen commitment requires two independent generators $G, H \in \mathbb{G}$ , and forms the commitment to $x$ as:

x \cdot G + r \cdot H

for some blinding factor $r \in \mathbb{F}_q$ .

One useful relation is proving that a value $X = x \cdot G$ , with $x$ hidden by a commitment $C$ :

\{(G, H, X, C; x, r)\ |\ x \cdot G = X \land x \cdot G + r \cdot H = C \}

As you might guess, this is in fact a Maurer relation, for the homomorphism:

\begin{aligned} &\varphi : \mathbb{F}_q^2 \to \mathbb{G}^2 \cr &\varphi(x, r) := (x \cdot G, x \cdot G + r \cdot H) \end{aligned}

Our challenge set can be $\mathbb{F}_q$ once again.

We can also have an arbitrary homomorphism, and not just $x \cdot G$ , which is thanks to the flexibility of Maurer proofs.

Oblivious PRFs

Another interesting example comes from the Privacy Pass paper ³.

In essence, a server knows a secret key $k$ that allows them to calculate a prf via:

P \mapsto k \cdot P

If you present $(P, Q)$ such that $Q = k \cdot P$ , then the server is convinced that it calculated that pair for you, since only it knows $k$ , and inverting the discrete logarithm is hard. In this paper, they use this to create redeemable tokens as an alternative to completing captchas.

They also want these tokens to be unlinkable, so they describe a protocol which allows getting such a pair $(P, Q)$ without revealing it to the server.

The idea is to send $P' := r \cdot P$ , have the server reply with $k \cdot P'$ , which you can then unblind to get $Q := r^{-1} \cdot k \cdot P' = k \cdot P$ .

One subtlety is that you need to make sure that the server actually used the same $k$ here that they've been using for other people.

One way to do this is for the server to publish $K := k \cdot G$ in advance, and then provide a proof for the relation:

\{(G, P', Q' ; k )\ |\ k \cdot G = K \land k \cdot P' = Q' \}

And, if you can believe it, this is an instance of a Maurer relation, with the homomorphism:

\varphi(k) := (k \cdot G, k \cdot P')

Attribute-Based Credentials

Attribute-based credentials are an amazing piece of technology which I won't have time to explain here. I will only use a little bit of the Pointcheval-Sanders scheme ⁴ here anyways.

Their scheme uses two proofs.

The first is for the relation:

\{(G, C, Y_1, \ldots, Y_n; t, a_1, \ldots, a_n) \ |\ C = t \cdot G + \sum_i a_i \cdot Y_i \}

This is, as you might have come to expect by now, an instance of a Maurer relation, with the homomorphism:

\varphi(t, a_1, \ldots, a_n) := t \cdot G + \sum_i a_i \cdot Y_i

The second proof they use is for the substantially more complicated relation:

\begin{aligned} &\{(\sigma_1, \sigma_2, \tilde{G}, \tilde{X}, \tilde{Y}_1, \ldots, \tilde{Y}_n ; t, a_1, \ldots, a_n) \ | \ \cr &e(\sigma_2, \tilde{G}) - e(\sigma_1, \tilde{X}) = t \cdot e(\sigma_1, \tilde{G}) + \sum_i a_i \cdot e(\sigma_1, \tilde{Y}_i)\cr &\} \end{aligned}

(Here $e$ denotes a pairing $\mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ )

I had to implement this for a class, and the first time I saw this, I was a bit taken aback.

That is, until I realized that this was an instance of a Maurer relation.

Indeed, all of the pairing stuff is really fluff, because those just become public values. If we squint a bit, we have:

\blacksquare = t \cdot \blacksquare + \sum_i a_i \cdot \blacksquare

But this part on the right is just a homomorphism of $t$ and $a_i$ , which we can write as:

\varphi(t, a_1, \ldots, a_n) := t \cdot e(\sigma_1, \tilde{G}) + \sum_i a_i \cdot e(\sigma_1, \tilde{Y}_i)

The output of this group is an element in $\mathbb{G}_T$ , so it suffices to take integers less than the smallest prime factor in the order of $\mathbb{G}_T$ as our challenge set.

TWW Polynomial Commitment Scheme

Finally, let's conclude our examples with a polynomial commitment scheme, which doesn't require any fancing pairings or trusted setups.

A polynomial $p$ of degree $d$ consists of $d + 1$ coefficients:

p_0 + p_1 \cdot X + \ldots + p_{d} \cdot X^{d}

Rather than an element of $\mathbb{F}\_q[X]\_{\leq d}$ , we can see this polynomial as a vector ${\bold{p} \in \mathbb{F}_q^{d + 1}}$ .

If we have $d + 2$ independent generators $H, G_0, \ldots, G_d$ , we can create a commitment scheme in the same way as for Pedersen commitments:

\text{Com}(p, r) := r \cdot H + \sum_i p_i \cdot G_i

One neat property of this scheme is that it's homomorphic with respect to its inputs $p$ and $r$ .

This is all fine and dandy, but not very useful unless we can create opening proofs.

This is a proof that:

\{(y, x, C; p, r)\ |\ \text{Com}(p, r) = C \land p(x) = y\}

In other words, the polynomial behind the commitment evaluates to $y$ at the point $x$ .

Now, the $\text{Com}(p, r)$ part is homomorphic, but what about the $p(x) = y$ part?

Well, one way to write $p(x)$ is as:

\sum_i p_i \cdot x^i

From here, it's clear that $p(x) + q(x) = (p + q)(x)$ :

(\sum_i p_i \cdot x^i) + (\sum_i q_i \cdot x^i) = \sum_i (p_i + q_i) \cdot x^i

Because of this, our opening proof is merely an instance of a Maurer relation!

The homomorphism we use is:

\varphi(p, r) := (r \cdot H + \sum_i p_i \cdot G_i, \sum_i p_i \cdot x^i)

And we can use $\mathbb{F}_q$ as our challenge set, once again.

The disadvantage of this scheme is that opening proofs are quite large.

The communication complexity is $|\mathbb{G}| + (d + 2) \cdot |\mathbb{F}_q|$ , because we need to send a group element and a scalar element as our first message (for the output of $\varphi$ ), and then we need to send our response, which consists of one scalar for each coefficient in our polynomial.

These disadvantages are why I call this the world's worst polynomial commitment scheme.

Conclusion

Hopefully I could impart to you some of the awe I've come to have for Maurer's paper. It's really a very neat gem with a surprising number of use cases. It's quite the shame that more people aren't aware of it!

We've seen how to use it for oblivious PRF proofs, for attribute-based credentials, for polynomial commitments, and of course, for the humble Schnorr signature.

I think you'll be able to find many more use-cases which I haven't mentioned in this post, such as final exams in cryptography courses :).

The paper itself is a pretty easy read, so you might want to check that out as well, along with the other references.