Version A: The simplest approach with a non-anonymous setting

• User's public key:
  $g^{f(0)}$
• User submits the commitment of the polynomial, its public key, and the opening proof:
  $g^{f(\alpha )},g^{f(0)},g^{{\psi }_0(\alpha )}$

The verifier checks if the user's public key is on the committed polynomial by verifying the opening of the KZG commitment:

$$e(g^{{\psi }_0(\alpha )},g^{\alpha })\cdot e(g,g^{f(0)})\stackrel{?}{=}e(g,g^{f(\alpha )})$$
If this check passes, the verifier trusts the public key and the commitment. However, this trust may be misplaced due to a vulnerability in the setup phase. The prover can manipulate the public key by choosing a random number

$\gamma$. The prover then multiplies

$g^{\psi (\alpha )}$ and

$g^{f(0)}$ with

$g^{\gamma }$ to produce

$g^{\psi (\alpha )}\cdot g^{\gamma }$ and

$g^{f(0)}\cdot g^{\alpha }\cdot g^{\gamma }$. This results in a manipulated pairing check that still passes. If the verifier attempts to interpolate the polynomial by Lagrange interpolation, they will get a private key that does not correspond to the crafted public key. This highlights a significant vulnerability in the setup phase of Version A.

The manipulated pairing check the verifier ends up checking is:

$$e(g^{{\psi }_0(\alpha )}\cdot g^{\gamma },g^{\alpha })\cdot e(g,g^{f(0)}\cdot g^{\alpha \cdot -\gamma })\stackrel{?}{=}e(g,g^{f(\alpha )})$$

Breaking down the left side of this equation:

1. Expand the pairing:

$$e(g^{{\psi }_0(\alpha )}\cdot g^{\gamma },g^{\alpha })\cdot e(g,g^{f(0)}\cdot g^{\alpha \cdot -\gamma })=e(g^{{\psi }_0(\alpha )},g^{\alpha })\cdot e(g^{\gamma },g^{\alpha })\cdot e(g,g^{f(0)})\cdot e(g,g^{\alpha \cdot -\gamma })$$

2. Use the property of bilinear pairings where
   $e(g^a,g^b)=e(g,g{)}^{ab}$:

$$=e(g,g{)}^{{\psi }_0(\alpha )\cdot \alpha }\cdot e(g,g{)}^{\gamma \cdot \alpha }\cdot e(g,g{)}^{f(0)}\cdot e(g,g{)}^{-\gamma \cdot \alpha }$$

3. Combine like terms:

$$=e(g,g{)}^{{\psi }_0(\alpha )\cdot \alpha +\gamma \cdot \alpha +f(0)-\gamma \cdot \alpha }$$

4. Recall that
   ${\psi }_0(\alpha )\cdot \alpha =f(\alpha )-f(0)$, so substitute:

$$=e(g,g{)}^{f(\alpha )-f(0)+\gamma \cdot \alpha +f(0)-\gamma \cdot \alpha }$$

5. Cancel out
   $f(0)$ and
   $\gamma \cdot \alpha$:

$$=e(g,g{)}^{f(\alpha )}$$

This is equal to the right side of the original equation

$e(g,g^{f(\alpha )})$, and hence the check passes. The prover successfully manipulates the values with

$\gamma$ while still passing the verification, leading to the vulnerability. The verifier ends up wrongly trusting the commitment associated with the false public key.

Why Pok can solve this?

Recall that in a Proof of Knowledge (PoK), the prover must convince the verifier that they possess knowledge of the secret value without revealing any information about the secret itself. This is achieved through a challenge-response protocol, where the verifier presents a random challenge to the prover, who must then provide a valid response.

Given the construction of the manipulated public key, the corresponding private key is

$f(0)-\alpha \cdot \gamma$. However,

$\alpha$ is a value from the Structured Reference String (SRS), and in a secure setup, this value is not known by the prover or any participant in the protocol, only the trusted setup coordinator knows it and should delete it after setup. Hence, the prover cannot construct the corresponding private key.

Therefore, if a verifier requests a PoK for the private key, the prover would be unable to provide a valid PoK. This is because constructing a valid PoK would require knowledge of both

$f(0)$ and

$\alpha$, and while the prover knows

$f(0)$, they do not know

$\alpha$. As a result, the prover would be unable to craft a valid response to the verifier's challenge, and the verifier would reject the prover's submission.

Thus, integrating a PoK protocol into this scheme would effectively prevent the described attack, as it would prevent the verifier from accepting a manipulated public key, addressing the vulnerability in the original setup.

In the Schnorr Proof of Knowledge (PoK) protocol, the prover generates a random number

$r$, and calculates

$R$ using the equation

$R=rG$. Here,

$G$ is the generator point of an elliptic curve group.

The verifier then sends a challenge number,

$c$, to the prover. In response, the prover sends back

$z$, calculated using the equation

$z=r+c\cdot \text{privateKey}$.

Finally, the verifier checks whether

$zG$ equals

$R+c\cdot \text{publicKey}$. If this equation holds true, the prover has successfully demonstrated knowledge of the private key without revealing it.

For the prover to provide a valid Proof of Knowledge (PoK) in a Schnorr-style protocol, they need to be able to correctly compute

$z=r+c\cdot \text{privateKey}$ and withstand the verifier's check of whether

$zG$ equals

$R+c\cdot \text{publicKey}$.

Given that the manipulated public key is

$g^{f(0)}\cdot g^{\alpha \cdot -\gamma }$, the corresponding private key is indeed

$f(0)-\alpha \cdot \gamma$. Since

$\alpha$ is securely hidden and not known to the prover, they are unable to compute the correct private key that corresponds to the manipulated public key.

Therefore, when challenged by the verifier, the prover would not be able to compute the correct response

$z$, since they cannot calculate

$f(0)-\alpha \cdot \gamma$ without knowing

$\alpha$. As a result, the verifier's check

$zG=R+c\cdot \text{publicKey}$ would fail, and the verifier would reject the prover's claim.