探索橢圓曲線配對_RIN:Aldrin

作者：VitalikButerin

原標題：《ExploringEllipticCurvePairings》

發表時間：2017年1月14日

密碼學的眾多基礎建設，例如「確定性閾值簽名」(deterministicthresholdsignature，暫譯)、zk-SNARKs與其他形式較簡單的零知識證明等等，背后關鍵的原始模型之一是橢圓曲線對。橢圓曲線在三十余年來廣泛使用于加密、數位簽章等密碼學應用，「橢圓曲線對(ECpairings)」是最近基于其上的新玩意，它引進了加密乘法，讓基于橢圓曲線的協定，所能做的事情大為增加。這篇文章會詳細地介紹橢圓曲線對，以及簡要解釋它如何運作。

因為這概念真的不容易，不太預期你讀第一遍甚至是第十遍時就真的完全理解，但希望這篇文章能至少告訴你一些箇中奧妙。

橢圓曲線本身就已經是一個不太容易理解的主題，但這篇文章大多時候會假設你對它的運作原理有些認識，如果你沒有基本概念的話，我會推薦這篇文章作為入門。總的來說，橢圓曲線處理的是一些稱為「點(points)」的數學物件，直白說是二維平面上的點(x,y)，以及一些加減運算的特別公式，你還可以讓點去乘以一個整數。

這是點的加法在圖上看起來的樣子

除此之外有個特別的點叫做「無窮遠點」(O)，在點的運算規則中作為零元素，也就是對于所有點都有P+O=P。一條曲線還擁有一個稱為「階(order)」的特質，也就是存在一個正整數n，對于所有P都使得P*n=O。還有某個事先協議好的「生成點(generatorpoint)G」，也就是挑選來作為加法單位元素、代表數字1那個角色的點。理論上任何曲線上的點都可以當生成元，重要的是那個G是統一選定的。

河北省將積極探索“區塊鏈+”在各領域運用:河北省科技廳日前印發《河北省數字經濟關鍵核心技術攻關專項行動計劃（2020-2022年）》。其中，專項行動計劃提出，在服務業數字化領域，積極探索“區塊鏈+”在各領域的運用。（河北新聞網）[2020/9/25]

配對就是進一步允許你驗證某類更復雜的等式：例如，如果P=G*p、Q=G*q、R=G*r，當你要檢查p*q=r是否成立，你只要有P,Q,R三個點的座標做為輸入就行了。這也許看起來像是橢圓曲線最基本的安全保證被打破了，因為乍看之下，要是知道P點的座標就泄漏了p的值。但事實上這樣泄漏的風險非常局限──準確來說，判定性的Diffie-Hellman問題很容易，但是計算性的版本仍然是「計算上不可行(computationallyinfeasible)」的。至少難度就跟不知道這個值差不多。

第三種理解「配對」的方式，也許是在我們討論的大部分使用情境里最有啟發性的方式是，如果你把橢圓曲線上的點看成一個單向加密函數，那么對比傳統橢圓曲線的數學原理讓你檢驗變數間的線性約束，橢圓曲線對就是讓你檢驗變數間的二次約束。能夠做到二次以后，就足夠讓我們做些像是確定性閾值簽名、QAP(quadraticarithmeticprograms，一種零知識證明)等等有趣的應用。

現在的問題是我們上面引進的e(P,Q)這個運算子到底是什么？這就是一組「配對」。數學家們有時候也把它叫做「雙線性映射」，「雙線性」在這里基本上表示它滿足以下條件：

e(P,Q+R)=e(P,Q)*e(P,R)e(P+S,Q)=e(P,Q)*e(S,Q)

注意到這里的+和*可以是任意的運算子；當你新建立一類數學物件的時候，抽象代數上不在意+和*是如何被「定義」的，只要和我們習以為常的運算一致就可以了，像是a+b=b+a、(a*b)*c=a*(b*c)、(a*c)+(b*c)=(a+b)*c。

聲音 | 聯想副總裁：聯想將區塊鏈技術與人工智能技術結合探索:據每日經濟新聞消息，近日，聯想集團副總裁徐飛玉接受采訪時表示，過去一年多時間，聯想全方位實施人工智能戰略，在智能語音、智能客服、智慧醫療等方面也出現了一系列研究成果。目前，聯想也將區塊鏈技術與人工智能技術結合探索。[2019/4/13]

假如現在P,Q,R,S僅僅是數字，那配對函數十分容易構造：我們可以定義e(x,y)=2^(xy)。那么我們就會看到：

e(3,4+5)=2^(3*9)=22?e(3,4)*e(3,5)=2^(3*4)*2^(3*5)=212*21?=22?

它確實是雙線性的！

然而像這樣簡單的配對不適合用在密碼學上，因為要分析單純運作在整數上的數學物件簡直輕而易舉；整數的性質使得除法、對數等等許多操作變得容易。整數也沒有「公鑰」或是「單向函數」的概念。進一步說，上面描述的那種配對是可逆的：知道x、知道e(x,y)，做個除法和對數就可以算出y。我們想要的數學結構是盡可能接近「黑盒子」：你可以做些加減乘除，但也就只能這樣了。這個時候橢圓曲線和橢圓曲線對就派上用場了。

人們發現，確實能在橢圓曲線的點上設計雙線性映射──也就是當輸入是橢圓曲線上的兩個點P和Q，構造一個函數e(P,Q)映射到一個F_p12的元素，但做到這件事情底下的數學實在是十分復雜。

第一，我們來介紹質數體(primefields)和擴體(extensionfields)。上圖畫的曲線雖然漂亮，但那是在你假設曲線的等式定義在平常所用的實數上才會長成那樣。如果我們真的在密碼學里使用實數，那你就可以用對數「倒回去」，那一切就沒用了，更何況儲存實數所需的空間可能會無盡地長。因此，我們改用實數體上的數字。

聲音 | Twitter首席執行官：Twitter正在探索區塊鏈的潛在應用:據Cointelegraph 9月7日消息，Twitter首席執行官杰克·多爾西(Jack Dorsey)在國會委員會作證時表示，該公司正在探索區塊鏈技術的潛在應用。杰克·多爾西在出席國會關于Twitter透明度和問責制的聽證會上回答了有關問題。當被問及區塊鏈技術對公司可能有哪些潛在應用，多西表示，區塊鏈可以用來打擊錯誤信息和騙局。[2018/9/7]

一個質數體由數字0,1,2,…,(p?1)所成集合構成，其中p是一個質數，而其運算由下定義：

a+b:(a+b)%p?a*b:(a*b)%p?a-b:(a-b)%p?a/b:(a*b^(p-2))%p

基本上，所有運算都在模(modulo)p下進行（這里有模運算的簡介)。除法是個特例。一般來說，3/2不是整數，但我們想要只處理整數，所以我們改成去找整數x使得x*2=3，而這里的*當然是指上面定義的模數乘法。幸虧有費馬小定理，除法的那個指數定義能滿足需要，但還有個更快的做法，那就是用擴展歐幾里得演算法。假設p=7，下面有幾個例子：

2+3=5%7=5?4+6=10%7=3?2-5=-3%7=4?6*3=18%7=4?3/2=(3*2^5)%7=5?5*2=10%7=3

如果你試著操作這樣的運算，你會發現它是前后一致的，而且滿足所有尋常的規則。最后的兩個例子說明(a/b)*b=a，你還可以發現(a+b)+c=a+(b+c)、(a+b)*c=a*c+b*c，還有其他你高中所知道和喜愛的代數等式都還會繼續運作。現實上使用的橢圓曲線，點和等式通常都是在質數體上運算的。

雷神科技將發布智能“礦機” 探索區塊鏈與游戲智能硬件新模式:“區塊鏈+游戲”概念火爆，包括網易、藍港互動等多家傳統公司宣布入場。據悉，“只為游戲而生”的互聯網游戲產業上市公司雷神科技也將布局區塊鏈，將在韓國TokenSky區塊鏈大會上發布有關“礦機”的智能產品。另外，雷神還將與新加坡拓撲基金會達成戰略合作。其創始人兼CEO路凱林將在大會上進行“探索區塊鏈與游戲智能硬件的全新模式”的主題分享。[2018/3/7]

現在我們來談談擴體。你先前可能已經看過擴體了，數學課本上最常遇到的例子是復數體──以實數體為基礎加入sqrt(-1)=i這個新的元素后擴張而成的。簡單來說，擴體就是在一個現成的體上，「發明」一個新的元素，并且定義好這個新元素跟現有的元素的關系（在剛剛的例子里的話是i^2+1=0)；這個關系式不能被現有的數字滿足，那把這個新元素加進「舊有的元素的所有線性組合(linearcombination)」組成的集合便是構造出來的集合。

我們也可以對質數體進行擴張；舉個例子，在模7的質數體里加入我們剛剛所說的i，那么我們有

(2+3i)+(4+2i)=6+5i?(5+2i)+3=1+2i?(6+2i)*2=5+4i?4i*(2+i)=3+i

最后的等式可能比較難以理解；其實那條等式的第一步是先把左邊的乘法做分配變成4i*2+4i*i，得到8i-4。因為我們是在模7的環境下做運算，這個數字就變成了i+3。至于除法的部份則是：

a/b:(a*b^(p^2-2))%p

這邊費馬小定理的指數從p變成了p2，當然也可以使用擴展歐幾里得演算法來更有效率地運算。因為對于在體中的任一個元素x都會有x^(p2?1)=1，所以我們稱(p2?1)為「體中乘法群的階」。

印度財長賈特里：將探索區塊鏈技術的使用:日前，印度財長賈特里表示：將探索區塊鏈技術的使用。[2018/2/1]

對于實數體，代數基本定理保證了它的二次擴體(quadraticextension)：復數體，是完備的──這個體不能再被擴張，因為所有可能的新元素j與現有的復數之間應該要滿足的數學關系，都有一個在體內的元素早已滿足。但在質數體中，就沒有這個問題，我們可以對其進行三次擴張(cubicextension)，高次擴張，甚至擴張再擴張等等。橢圓曲線就是建立在這些模運算的復數上的。

對這些數學如何實作成程式碼有興趣的話，這邊有一些實作質數體以及擴體的例子。

回頭來看橢圓曲線對。橢圓曲線對是一個G2×G1→Gt的映射，其中：

G1是一條橢圓曲線，線上的點滿足形如y2=x3+b的式子，而且點的x,y座標都是F_p的元素。

G2也是一條橢圓曲線，同樣滿足G1的曲線，但G2中的元素的x,y座標是F_p12的元素

Gt是橢圓曲線的運算結果形成的集合。在我們討論的曲線中，Gt是F_p12

它主要必須滿足的性質是雙線性，在這個脈絡下這樣代表：

e(P,Q+R)=e(P,Q)*e(P,R)e(P+Q,R)=e(P,R)*e(Q,R)

選擇配對函數還有兩個重要的準則：

運算要足夠有效率

非退化

所以我們該怎么做到這件事？

讓配對函數得以運作背后的數學十分困難，而且需要一些進階的代數，超過我們目前為止所見，但我會大致說明。首先我們需要定義「因子(divisor)」的概念，基本上是另一種方式來表示作用在橢圓曲線上的點的函數們。一個函數的因子基本上計算了一個函數有多少個零點和取值無限大的點。為了理解清楚一些，我們來看看幾個例子。讓我們選定一個點P=(P_x,P_y)，然后考慮以下函數：

f(x,y)=x?P_x

它的因子是+?2*。原因如下：

這個函數在P點的值等于零，因為x取值P_x，所以x?P_x=0

這個函數在?P點的值等于零，因為?P和P的x座標相同

這個函數在x趨向無限大的時候也趨向無限大，所以我們說這個函數在O點取值無限大。計算這個無窮遠點要算兩次，所以O要乘以乘數-2。

計算上的理由大約是：因為這個曲線的方程式是x3=y2+b，當x增加，為了讓y2達到相當的規模，y增長的速度大約需要是x的1.5倍。因此如果一個線性函數只包含x，那它無限大那一項的乘數是2，但如果它包含y，那乘數就要是3。

現在考慮一條線的函數：

ax+by+c=0

其中a,b,c被選定來讓這條線通過點P和點Q。根據橢圓曲線加法的運作方式，它也一定會通過?P?Q這個點。因為它跑向無限大時會同時取決于x和y，所以因子是++?3*。

我們知道所有「有理函數」唯一地對應到某個因子，頂多就是多乘一個常數。

對于任意兩個函數F和G，(F*G)的因子等于F和G的因子之和，所以比如f(x,y)=P_x?x，那么(f3)=3*+3*?6*；P和?P算三次是因為在特定的數學意義下f3會「三倍快地」靠近0。

留意有個定理說如果你把某個因子的「方括號」拿掉，那些點運算后的結果必定是O，而且任何有這個性質的因子就會是那個函數的因子。

現在我們可以開始看Tatepairing了。考慮以下用因子定義的函數：

(F_P)=n*?n*，其中n是G1的階數，也就是對于所有P，n*P=O

(F_Q)=n*?n*

(g)=??+

現在，讓我們看看這個乘積F_P*F_Q*g^n。它的因子是：

n*?n*+n*?n*+n*?n*?n*+n*

化簡會得到干凈的：

n*?n*

注意到這個因子的格式跟F_P和F_Q的因子相符。因此有F_P*F_Q*g^n=F_(P+Q)。

現在再多做一個稱為「最終指數(finalexponentiation)」的操作，把前述運算的結果自乘到z=(p12?1)/n的冪次，其中p12?1是F_p12中乘法群的階。注意到如果你把這個指數套用在任何已經是n次冪的結果上，你就會得到某個元素的(p12?1)次方，結果就會變成1。因此，在最后的指數步驟后，g^n會消掉，然后我們就會得到F_P^z*F_Q^z=F_(P+Q)^z。于是就有了雙線性的性質的一部分。

現在如果你想構造一個函數，它在兩個參數上都會是雙線性的，你需要更嚇人的數學，那么要做的不只是算F_P，還要計算F_P的因子，再做下去就會得到完整的Tatepairing。為了證明更多結論你需要理解一些概念像是「線性等價(linearequivalence)」以及Weilreciprocity之類。這些概念詳細的內容可以在這里以及這里看到。

而這邊實作了一個Tatepairing的修改版──OptimalAtePairing。該代碼里還實現了用米勒算法來計算出F_p。

事實上，使用這樣的配對如同提起一把雙面刃：一方面這代表著我們可以利用這種配對實現不同的協定，同時也代表了我們在選擇使用什么橢圓曲線時要特別小心。

每個橢圓曲線都有一個叫embeddingdegree的值──最小的整數k使得p^k?1是n的倍數。在上文提到的體當中k=12，在傳統的橢圓曲線密碼學中使用的體的embeddingdegree通常都會非常大，大到讓計算出配對這件事是計算上不可行的。不過，當我們不注意的時候很有可能會構建出k=4甚至k=1的體。

當k=1的時候，橢圓曲線上的「離散對數問題」可以退化成一個在F_p上的相對簡單的問題；使用一個embeddingdegree大于等于12的橢圓曲線會保證這種退化不可行，又或者是退化出來的問題復雜到至少跟用「正常」的方法從公鑰算出私鑰一樣困難。現在所有標準的曲線參數都經過仔細檢查，不會受這個問題影響。

Tags：區塊鏈INGRINRING區塊鏈通俗易懂的例子WB-MiningAldrinUpfiring

SOL