This week we look at what the BLS pairing-based signature scheme is. See here for full details.
This signature scheme makes use of the Weil pairing on elliptic curves, essentially a bilinear form (with multiplicative notation) on points of order dividing n on a curve, taking values in n^{th} roots of unity.
So assume you have an elliptic curve E/\mathbb{F}_{3^l}, following the notation in the original paper. The scheme is as follows:
KeyGen: Let E/\mathbb{F}_{3^l} be an elliptic curve and q be the largest prime factor of the order of the curve. Let P be a point on it of order q and x \in \mathbb{Z}_q^* be selected at random. Finally let R = xP. Then output (l, q, P, R) as the public key and x as the secret key.
Sign: To sign a message M \in \{0,1 \}^* we map M to a point P_M in <P>. This is done via an algorithm h described in section 3.3 of the paper, and is a hash function. Then let S_M = xP_M. The signature \sigma is the x-coordinate of the point S_M, and \sigma \in \mathbb{F}_{3^l}.
Verifiy: Given a public key (l, q, P, R), a message M and a signature \sigma, do:
This signature scheme makes use of the Weil pairing on elliptic curves, essentially a bilinear form (with multiplicative notation) on points of order dividing n on a curve, taking values in n^{th} roots of unity.
So assume you have an elliptic curve E/\mathbb{F}_{3^l}, following the notation in the original paper. The scheme is as follows:
KeyGen: Let E/\mathbb{F}_{3^l} be an elliptic curve and q be the largest prime factor of the order of the curve. Let P be a point on it of order q and x \in \mathbb{Z}_q^* be selected at random. Finally let R = xP. Then output (l, q, P, R) as the public key and x as the secret key.
Sign: To sign a message M \in \{0,1 \}^* we map M to a point P_M in <P>. This is done via an algorithm h described in section 3.3 of the paper, and is a hash function. Then let S_M = xP_M. The signature \sigma is the x-coordinate of the point S_M, and \sigma \in \mathbb{F}_{3^l}.
Verifiy: Given a public key (l, q, P, R), a message M and a signature \sigma, do:
- find a point S on the curve of order q whose x-coordinate is \sigma and whole y-coordinate belongs to \mathbb{F}_{3^l}. If no such point exists, reject the signature as invalid.
- set u = e(P, \phi(S)) and v = e(R, \phi(h(M))), where e is the Weil pairing on the curve and \phi is an automorphism E \leftarrow E. h is the same h mentioned earlier.
- if either u = v or u^{-1} = v accept the signature as valid; reject otherwise.
No comments:
Post a Comment