# Zero knowledge proof for GCD

Let A(x) and B(x) be two secret polynomials. Suppose a user publishes commitments $$C_A$$ and $$C_B$$ to these polynomials (such that the lengths of $$C_A$$ and $$C_B$$ are sublinear in the degree of $$A(x)$$ and $$B(x)$$). I would like to prove that the GCD of these two polynomials, (given the commitments) is 1. Is there a special scheme that proves such statement (i.e., not a NIZK for a general computation such as zk-SNARK)?

A simpler version of the above, is there a scheme that only proves (in zero knowledge) that GCD(a,b)=d? where a,b are secret integers, but a user publish the corresponding commitments ($$c_a$$ and $$c_b$$), and d is also public

• For the first problem with the polynomials, do you mean that the polynomials are public? If it would be interesting to check whether the prover can cheat and under which security model. If the polynomials are public I don't think that the problem is meaningful, since the gcd can be computed in logarithmic in the size of the polynomials time. Dec 28, 2022 at 16:26
• You are right, they are not. I should revise the question. Dec 28, 2022 at 16:32

## 1 Answer

Let's use the Kate, Zaverucha, Goldberg (KZG) polynomial commitment scheme to solve your problem. For the sake of simplicity, let's assume that we have a Type-1 pairing, i.e., both source groups are the same: $$e:\mathbb{G}\times\mathbb{G}\rightarrow\mathbb{G}_T$$. The structured reference string has the form $$\mathsf{srs}=\{g,g^{\tau},g^{\tau^2},\dots,g^{\tau^d}\},$$ where $$\tau\in_{R}\mathbb{F}_p$$ is the secret randomness obtained from the trusted setup.

The KZG commitment of a polynomial $$A(x)\in\mathbb{F}^{\leq d}_p[x]$$ will be the group element $$g^{A(\tau)}\in\mathbb{G}$$, that can be computed using the $$\mathsf{srs}$$ even though $$\tau$$ is not known.

If $$gcd(A(x),B(x))=1$$, then there exist $$C(x)$$ and $$D(x)$$ such that $$A(x)C(x)+B(x)D(x)=1$$. These polynomials (or integers in the simpler case of your question) are called Bezout-coefficients. We want to check this equation in the exponent in $$\tau$$, i.e., we check this polynomial equality at a single random point $$\tau$$ not known by the prover: $$A(\tau)C(\tau)+B(\tau)D(\tau)=1$$. Specifically, the proof $$\pi$$ will be the KZG commitments to $$C(x)$$ and $$D(x)$$, i.e., $$\pi=(g^{C(\tau)},g^{D(\tau)})$$. The prover can compute these polynomials $$C(x),D(x)$$ if indeed $$gcd(A(x),B(x))=1$$.

How can the verifier check the validity of the proof? Given the commitments $$(g^{A(\tau)},g^{B(\tau)})$$ and the proof $$\pi=(g^{C(\tau)},g^{D(\tau)})$$ the verifier checks $$e(g^{A(\tau)},g^{C(\tau)})e(g^{B(\tau)},g^{D(\tau)})\stackrel{?}{=}g_T$$, where $$g_T$$ is the generator of the target group $$\mathbb{G}_T$$.

Let's analyze the devised proof system.

• Correctness: $$e(g^{A(\tau)},g^{C(\tau)})e(g^{B(\tau)},g^{D(\tau)})=e(g,g)^{A(\tau)C(\tau)}e(g,g)^{B(\tau)D(\tau)}=e(g,g)^{A(\tau)C(\tau)+B(\tau)D(\tau)}=e(g,g)=g_T$$
• Soundness: The Bezout-coefficients exist if and only if $$gcd(A(x),B(x))=1$$.
• Zero-knowledge: this is left as an exercise to the astute reader. :)