52 Things, Number 50: What is the BLS pairing-based signature scheme?
52件事，第50号：什么是基于BLS配对的签名方案？
This week we look at what the BLS pairing-based signature scheme is. See here for full details.本周我们来看看什么是基于BLS配对的签名方案。请参阅此处了解详细信息。
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 nth roots of unity.
该签名方案利用了椭圆曲线上的Weil配对，本质上是曲线上除 n 的阶点上的双线性形式（带乘法符号），取 nth 单位根中的值。
So assume you have an elliptic curve E/F3l, following the notation in the original paper. The scheme is as follows:
假设你有一条椭圆曲线 E/F3l ，遵循原始论文中的符号。方案如下：
KeyGen: Let E/F3l 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∈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.
KeyGen：设 E/F3l 是一条椭圆曲线， q 是该曲线阶数的最大质因子。设#2是其上的一个点，顺序为#3，随机选择#4。最后让 R=xP 。然后输出 (l,q,P,R) 作为公钥，输出 x 作为密钥。
Sign: To sign a message M∈{0,1}∗ we map M to a point PM in <P>. This is done via an algorithm h described in section 3.3 of the paper, and is a hash function. Then let SM=xPM. The signature σ is the x-coordinate of the point SM, and σ∈F3l.
签名：要对消息 M∈{0,1}∗ 进行签名，我们将 M 映射到 <P> 中的点 PM 。这是通过论文第3.3节中描述的算法#4完成的，并且是一个散列函数。然后让 SM=xPM 。签名 σ 是点 SM 和 σ∈F3l 的 x 坐标。
Verifiy: Given a public key (l,q,P,R), a message M and a signature σ, do:
验证：给定公钥 (l,q,P,R) 、消息 M 和签名 σ ，请执行以下操作：
- find a point S on the curve of order q whose x-coordinate is σ and whole y-coordinate belongs to F3l. If no such point exists, reject the signature as invalid.
在顺序为 q 的曲线上找到一个点 S ，其#2坐标为 σ ，整个#4坐标属于 F3l 。如果不存在这样的点，则以无效为由拒绝签名。 - set u=e(P,ϕ(S)) and v=e(R,ϕ(h(M))), where e is the Weil pairing on the curve and ϕ is an automorphism E←E. h is the same h mentioned earlier.
集合 u=e(P,ϕ(S)) 和 v=e(R,ϕ(h(M))) ，其中#2是曲线上的威尔配对，#3是自同构 E←E 5#与前面提到的 h 相同。 - if either u=v or u−1=v accept the signature as valid; reject otherwise.
如果 u=v 或 u−1=v 中的任何一个接受签名为有效；否则拒绝。