第五十個知識點：什麼是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}\)，那麼就接受這個簽名，否則拒絕這個簽名。