Key pairing over BN-curves

Key pairing over BN-curves

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×x,p×y). In this way we get P=p×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×p, Q=G×q and R=G×r, we can check to see if r=p×q, but where we only know P, Q and R (the public values). At the current time we cannot compute p from P=p×G, even if we know P and G. The exposure of the values is limited as we can calculate R=G×p×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×pt. This is the signature. Bob then generates his public key by multiplying his private key (priv) by G to give priv×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×pt. She also takes the signature (sig) and multiples it by G to get sig×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: