Content
@
0 reply
0 recast
0 reaction
Zk
@risotto
ZK Scholars Assembly Revision 2 - Elliptic Curve & Schnorr Signature Elliptic curve can be simply described as the equation y^2 = x^3 + ax + b (mod p). This normal form is also called Weierstrass Form. Different elliptic curves are formed by changing the value of a, b and p. We can define elliptic curve points as a group but more interestingly, we can also do geometric operations with it. For example, the inverse -P of a point P is the one symmetric across the other side of x-axis. We can also do geometric addition to compute the sum of two points P and Q by drawing a line passing through both of them, the 3rd intersection point of this line will be R, and the inverse -R is the sum of P + Q because P + Q + R = 0 thus P + Q = -R in abelian group. To compute P + P, we draw a tangent line on point P and the inverse of next intersection point is the sum of those.
1 reply
0 recast
0 reaction
Zk
@risotto
By picking a generator point G from elliptic curve, we can now hide a scalar value a in G by multiplying them together aG or as an exponent G^a. Thanks to discrete logarithm problem, it is hard to extract a from aG / G^a. This enables encryption of secret value into a public sharable point and creates cryptography applications such as ELGAMAL, Schnorr Signature and ECDSA. In ELGAMAL, to encrypt an encoded message M, a random k is chosen and compute ciphertext pairs (C1, C2) as follows: C1 = k * G C2 = M + k * B B is the public key of Bob with secret key b s.t. B = bG To decrypt the message M, Bob just has to do C2 - b * C1. By substituting (C1, C2) and B we get: M + k * bG - b * k * G Notice that now the equation cancel off everything and leaving only M!
1 reply
0 recast
0 reaction
Zk
@risotto
In Schnorr Signature, given parameters: Private key = p Public key = P Challenge = e If the signature is s = p * e, it is very easy to retrieve p by doing p = s / e. To solve that problem, we add a random nonce r, share its public nonce R = rG and the signature becomes (s, R) where s = r + p * e. To verify the signature we do scalar multiplying s with G: sG = R + P * e Again by substituting we get: (r + p * e)G = rG + pG * e rG + peG = rG + peG Both sides equal! In ECDSA, using same parameters, choosing random nonce k, and taking only x coordinate as its public nonce r = (kG).x, signature s = 1 / k (e + p * r). To verify simply try recover kG and compare r: (e / s) * G + (r / s) * P = ((e + rp) / s) * G = kG If resulting x coordinate (kG).x = r then the signature is accepted. Next thread we going to explore how pairings & KGZ work!
0 reply
0 recast
0 reaction
