Score:2

Crypto

How to convert exponents and group operations to gates in arithmetic circuit

Z. Chen

8/3/24, 8:19 AM

I am following Vitalik Buterin's article to study zk-SNARKs recently.

I can understand the main procedure of zk-SNARKs when given example equation x**3 + x + 5 == 35. However, in cryptography, most equations contain exponents. For example, the prover may want to prove the knowledge of $a$ in $g^a=A$. In this case, an arithmetic circuit seems hard to be built by multiplication gates (since the number of multiplication gates is not fixed).

Then I think of elliptic curve, which can transform $g^a=A$ into $a\cdot g=A$ where $g$ is an elliptic curve point. By doing so, it suits the *form of multiplication gate. But this brings up another problem: the multiplication is actually an elliptic curve operation instead of basic arithmetic.

Therefore, I wonder how exponents and group operations can be transformed into arithmetic circuits.

1 + 3

zero-knowledge-proofs

arithmetic-circuit

Gareth Ma

8/9/24, 5:53 AM

Does this answer your question? [Zero knowledge proof for a discrete logarithm](https://crypto.stackexchange.com/questions/61741/zero-knowledge-proof-for-a-discrete-logarithm)

Z. Chen

8/10/24, 8:02 AM

@GarethMa Thanks. But that is not exactly what I am looking for. I know there are simple ZKPs for a discrete logarithm. My question is: if I want to prove the knowledge of discrete logarithm using zkSNARKs, I have to convert it into an arithmetic circuit at the setup phase. So, how can I convert the exponent (or logarithm) to an arithmetic circuit with only addition and multiplication gates?

Gareth Ma

8/10/24, 11:15 AM

AFAIK you can't?

Score:1

Crypto

user93353

8/10/24, 11:41 AM

$1)$ Why no exponentiation provided?

$A)$ Exponentiation is multiplication.

$5^4 = 5\star5\star5\star5$ (4 times)

So any exponentiation can be done using the multiplication gate

$2)$ How do scalar multiplication in elliptic curves using the addition & multiplication gates?

$A)$ First of all, there is no multiplication operation in the Elliptic Curve Group - the Elliptic Curve group supports only the addition operation. Scalar multiplication is actually addition. Elliptic Curve Group has formulas for addition of two points & also point doubling (doubling is addition of a point to itself).

Assuming $P=(x_1,y_1)$, $Q=(x_2, y_2)$, then you can compute

Addition ($P \ne Q$)

$R= (x_3, y_3) = P + Q$

Doubling (Addition where $P = Q$)

$R = 2P = 2Q = P + Q$

There are formulas for this

If you check the formulas it involves numerical addition & subtraction (which can be done with the addition gate of a circuit.

The division is actually multiplication by the inverse. So you have first calculate the inverse of $(x_2 - x_1)$ or $2y_1$ first in the finite field which again needs to be broken into basic operations (numerical addition/multiplication). And then the whole formula becomes something which can be just done using addition & multiplication gates.

So the addition, scalar multiplication etc are all notational operations which have to be broken down to basic arithmetic operations & then are done using circuit gates.

+ 3

Z. Chen

8/10/24, 12:10 PM

1) Why no exponentiation provided? Indeed exponentiation can be done using the multiplication gate. But things are different when using zkSNARKs. In zkSNARKs, the witness (hidden information) should be the input of a circuit. E.g. $5^4=625$ where 4 is the witness. And the circuit itself is public. Then obviously, if I give a circuit containing 4 multiplication gates of the same input 5, anyone would know my witness. 2) The formulas solve my second question. I can see basic arithmetic operations can be used to do scalar multiplication.

Z. Chen

8/10/24, 12:20 PM

And may I ask a little additional question: Changing the exponent operations in $Z_p$ to scalar multiplications of elliptic curve group for the purpose of using zkSNARKs is just my idea. Does it really work like this in reality?

user93353

8/10/24, 12:25 PM

In group theory, the multiplication & additional operations are actually notational - they may not actually mean addition or multiplication. As you see in Elliptic curve groups, addition is actually some other formula & not arithmetic addition. Even there some choose to write the scalar multiplication $nG$ as $G^n$ - you will find lots of cryptographic documents which use $G^n$ for scalar multiplication even though there is no actual exponentiation (there is even no notational exponentiation in a additive group). In group theory all operations are notational.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How to convert exponents and group operations to gates in arithmetic circuit

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.