BLS簽名

記e: G*G->G’，為一個非退化的雙線性映射，G和G’為素數r階的乘法群，生成元為g。根據雙線性映射的性質，e(g1^x, g2^y)=e(g1,g2)^(x*y)。要求在G上，CDH problem是困難的。

BLS簽名的三個函數

KeyGen：選取[0, r-1]內的一個隨機整數x，作為私鑰sk；g^x作為公鑰pk。由于CDH問題是困難的，我們相信DL問題也是困難的（雖然這一點還沒有證明），從pk無法計算得到x。

Signing：消息h的簽名為sig=h^x

Verification：驗證者知道G、g^x（即pk）、h、sig’。為了驗證sig’=h^x，即簽名是擁有私鑰x的人產生的，驗證者計算e(g, h^x)與e(g^x,sig’)，并判斷是否相等，相等則簽名得到驗證。

證明：若e(g^x,h)=e(g,sig’)，由于G是素數階的，h也是生成元，設sig’=h^y，則

由于e(g^x,h)=e(g,h)^x，且e(g,sig’)=e(g,h^y)=e(g,h)^y，則有e(g,h)^x=e(g,h)^y

由于G’群也是素數r階群，故有x=y，即sig’=h^x=sig，是由擁有私鑰x的人產生的。

?

基本思想是，可以利用雙線性映射e的性質，在不泄露x的情況下來驗證sig’==h^x

BLS簽名