Zero knowledge proof for GCD

Question

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

Answer 1

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. :)