第五十个知识点：什么是BLS基于对的签名方案？

BLS签名方案使用了椭圆曲线上了Weil对，本质上是一个在曲线上除n划分的双线性形式，使用 \(n^{th}\) 个单位根。

假设我们有一个椭圆曲线\(E/F_{3^l}\)，根据原始论文中的记号，方案如下描述：

密钥生成：让\(E/F_{3^l}\)是一个椭圆曲线，\(q\)是这个曲线阶数的最大因数。让\(P\)是其中的一个阶数是\(q\)的点，然后随机的选择\(x \in Z_q^*\)。最后让\(R = x \cdot P\)。那么输出\((l,q,P,R)\)作为公钥，\(x\)作为私钥。

签名：为了签名消息\(M \in \{ 0,1 \}^*\)。我们将\(M\)映射到一个在椭圆曲线群子群\(<P>\)中的一个点\(P_M\)。这可以通过一个\(hash\)函数来进行这样的签名。然后让\(S_M= x \cdot P_M\)。签名\(\sigma\)就是点\(S_M\)的\(x\)轴坐标，同时满足了\(\sigma \in F_3^{l}\)。

验证：给定一个公钥\((l,q,P,R)\)，一个消息\(M\)和一个签名\(\sigma\)，做下面的算法：

• 找到椭圆曲线上的一个阶数为\(q\)的点\(S\)，它的横坐标是\(\sigma\)，纵坐标在\(F_{3^l}\)中，如果不存在这样的点，那么拒绝这个签名。

• 令\(u = e(P,\phi(S))\)，同时\(v = e(R,\phi(h(M)))\)，其中\(e\)是Weil对中的映射，\(\phi\)是一个\(E \leftarrow E\)的同态，\(h\)就是之前提到的函数。

• 如果\(u = v\)或者\(u = v^{-1}\)，那么就接受这个签名，否则拒绝这个签名。