Fake proving/verifying key

[hussein-aitlahcen]

Hi, I have a quick question: assume I generate a circuit and a pk/vk with gnark and then tweak a part of the pk or vk key. Would anyone be able, given the circuit and the pk/vk pair, to determine, without proving, that they are valid for the circuit? Or are they completely unrelated and guessing is impossible?

[ivokub]

I haven't thought about this way. My initial hunch is that it is not possible to determine.

What imo can be done is to generate a proof of correctness of the proving key. Imo this is usually done for MPC ceremonies to ensure that the participant has contributed their share correctly. And then, if there is a proof of correctness, then it won't be possible to modify existing pk key.

[hussein-aitlahcen]

I think it's possible for Plonk. IIRC in Plonk the proving and verifying keys are both deterministically derived from the KZG SRS, so it remains to verify the latter, which I believe can be done with a sequence of pairing checks. The SRS consists of [1]2,[x]2 and a sequence g0,g1,...,gN which is correct iff gn=[xn]1 for all 0≤n≤N. We can first check that g0=[1]1, and then and for 0<n≤N that e(g_n, [1]_2) = e(g_{n-1}, [x]_2) (sorry, for some reason github refuses to render g_{n-1}. By induction we can assume g_{n-1} = [x^{n-1}]_1 which eventually gives gn=[xn]1.

Thanks a lot, I forgot to specify that I was looking at Groth16. I at least know that Plonk is disqualified here.

[hussein-aitlahcen]

Let me precise a bit more what I am looking for here:

1. Assume we trust a party to generate many proving/verifying keys for the same circuit (no multiparty computation).
   I receive the vector of keypairs and the circuit. If I don't have any valid input for the circuit:
   Is a valid proof generated with a fake proving key indistinguishable from an invalid proof generated with a valid proving key? In other words, I am able, without proving, to determine if any keypair is valid/invalid?

I expect the above to be indistinguishable but not sure at all.

More specifically, only a user that is able to prove (having valid inputs for the circuit) can determine whether a keypair is valid/invalid because of the result being either $1_{G_T}$ or a random $x_{G_T}$ value?

If so, given a private message $M \in \mathbb B^*$, we (the trusted party) should be able to encrypt the message for a witness of the problem the circuit expect one to solve (generate $V = gen(C, sizeInBit(M))$ keypairs, where the pair $V_i$ is valid iif $M_i = 1$)? I thought about this possibility after reading the following paper about Witness Encryption. I have a working POC with gnark, but unsure whether the above property 1) hold...

[Tabaie]

Fascinating problem! I think they are distinguishable. Taking
from the paper, we can use the KZG-esque methods from above to verify the consistency of the ${x^i}$ in $\sigma_1$ and $\sigma_2$. Checking that $\beta,\delta$ are consistent is also straightforward. To verify the correctness of $\frac{\beta u_i(x)+\alpha v_i(x)+w_i(x)}{\gamma}$ we can compute $e(\beta, u_i(x)).e(\alpha,v_i(x)).e(1,w_i(x))$ and see if it is equal to $e\Big(\frac{\beta u_i(x)+\alpha v_i(x)+w_i(x)}{\gamma}, \gamma\Big)$ as given in $\sigma_1$. The $\frac{\beta u_i(x)+\alpha v_i(x)+w_i(x)}{\delta}$ can be verified similarly. Finally we can construct $e(x^i, t(x))$ and see if it matches $e\Big(\frac{x^it(x)}{\delta},\delta\Big)$ as given in $\sigma_1$.
I'm not very confident about this so please lmk if it doesn't make sense.

[hussein-aitlahcen]

@Tabaie I think you destroyed my hope haha. Your maths makes sense to me :). I'm going to write a small snippet to check validity of keypairs as per your suggestion and let you know. Many thanks!

[Tabaie]

😅 you're very welcome! Please let me know how it goes (especially interested in how many pairings can be batched)