Elliptic Curve key pairing is also used with zk-SNARKs and zero-knowledge proofs. It can be used for "encrypted multiplication".
Key pairing over BN-curves
[Pairing Home][Home]
Elliptic curves are used fairly extensively in public key encryption (such as in Bitcoin and Tor). A BN-curve (Barreto-Naehrig curve) [paper] defines an elliptic curve which can be used for pairings that allow for a high security and efficiency level. This page uses pairings over a 256-bit BN curve and derives a signature for a message.
Elliptic Curve key pairing is also used with zk-SNARKs and zero-knowledge proofs. It can be used for "encrypted multiplication". |
For an Elliptic Curve we generate a 256-bit random number for the private key (\(p\)), and then take a point (\(G\)) [x,y] on the Elliptic Curve and then multiply it by the private key to get another point \( (p \times x,p \times y)\). In this way we get \(P = p \times G\), and where \(G\) is a known point on the Elliptic Curve, \(P\) is our public key and \(p\) is our private key.
With pairings we can derive more complex relationships between the points, such as if \(P = G \times p\), \(Q = G \times q\) and \(R = G \times r\), we can check to see if \(r = p \times q \), but where we only know P, Q and R (the public values). At the current time we cannot compute \(p\) from \(P = p \times G\), even if we know \(P\) and \(G\). The exposure of the values is limited as we can calculate \(R = G \times p \times q\), and where it is not possible to determine \(p\) or \(q\).
The following code integrates the BN-256 code. Let's test the code by simply creating a signature for a message. Bob will take a message and create a signature with his private key, and Alice will prove it with his public key.
First we take the message and hash it to a point on the elliptic curve (pt). Next we take the private key (priv) - a random 256-bit value - and multiple the point to give \(priv \times pt\). This is the signature. Bob then generates his public key by multiplying his private key (priv) by G to give \(priv \times G\). Alice will then take the message and hashes it to a point on the elliptic curve (pt). Next she multiplies this by Bob's public key to get \(pub \times pt\). She also takes the signature (sig) and multiples it by G to get \(sig \times G\). If the signature is correct, the two values generated should match.
In the following we take a message of "hello":
Message: hello ====================== Private key: 30004356452222922383849933778039944452315749064290473682127167271568896730865 Public key: ((51034946685813001170817435102353414123470700731734176493660185826748147116266,64210743524728530290185905551942812616400571488225773882109119010482573127691), (15434778760021406666927668640057214805094329177828734336347158339868964471406,1645883428099392092679734410866463344800887723192890577720280731380716208522)) ====================== Point for message (Pt): (16401638554737542226905570806322043806622525723234854083744567922111527431480, 25777301830215238716230693428646242503120247217966455808892851140680930083168) Signature (p x Pt): (40232397439089775236199104399906464299782864194117440302779943704748308206467L, 0L) Signature verified
The code uses the BN-256 code [here]:
import bn256 msg="hello" # Get public key and random private key priv,pub = bn256.g2_random() print("Message:\t",msg) print("\n======================") print("Private key:\t",priv) print("Public key:\t",pub) # Get signature pt = bn256.g1_hash_to_point(msg) assert pt.is_on_curve() sig=bn256.g1_compress(pt.scalar_mul(priv)) print("\n======================") print("\nPoint for message (Pt):\t",pt) print("Signature (p x Pt): ",sig) # Verify signature unsig = bn256.g1_uncompress(sig) assert type(pub) == bn256.curve_twist assert type(unsig) == bn256.curve_point msg_pt = bn256.g1_hash_to_point(msg) assert msg_pt.is_on_curve() rtn1 = bn256.optimal_ate(pub, msg_pt) rtn2 = bn256.optimal_ate(bn256.twist_G, unsig) if (rtn1 == rtn2): print("\nSignature verified") else: print("\nSignature not verified")
The following is a presentation on the subject: