Skip to main content
Became Hot Network Question
added 298 characters in body
Source Link
Doron
  • 99
  • 6

Let aA(x) and bB(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 thethese two polynomials, (given the commitments) is 1. Do you know ifIs there is a special scheme that proves such statement (i.e., not a NIZK for a general computation such as zk-SNARK)?

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

Let a(x) and b(x) be two polynomials. I would like to prove that the GCD of the two polynomials is 1. Do you know if there is a special scheme that proves such statement (i.e., not a NIZK for a general computation such as zk-SNARK)?

Is there perhaps a simpler version that only proves (in zero knowledge) that GCD(a,b)=d for public integers a,b,d?

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

Source Link
Doron
  • 99
  • 6

Zero knowledge proof for GCD

Let a(x) and b(x) be two polynomials. I would like to prove that the GCD of the two polynomials is 1. Do you know if there is a special scheme that proves such statement (i.e., not a NIZK for a general computation such as zk-SNARK)?

Is there perhaps a simpler version that only proves (in zero knowledge) that GCD(a,b)=d for public integers a,b,d?