年曉宇，游　林

(杭州電子科技大學(xué)密碼與信息安全研究所，浙江 杭州 310018)

?

基于三類代數(shù)曲線上的雙線性對(duì)實(shí)現(xiàn)

年曉宇，游林

(杭州電子科技大學(xué)密碼與信息安全研究所，浙江 杭州 310018)

摘要：雙線性對(duì)中，最常見的是Tate對(duì)，Eta對(duì)和Ate對(duì)是Tate對(duì)的變種.針對(duì)橢圓曲線y2+y=x3+x+b，其中b∈2，通過分類討論，給出了4種情況下的Tate對(duì)和Eta對(duì)實(shí)現(xiàn)算法.同時(shí)，還提出了基于超橢圓曲線y2+y=x5+ax+b(其中a,b∈2)上的Tate對(duì)和Ate對(duì)實(shí)現(xiàn)算法，以及基于超橢圓曲線y2=xp-ax-b(其中a,b∈p)上的Ate對(duì)實(shí)現(xiàn)算法.為基于雙線性對(duì)密碼體制的研究和應(yīng)用提供了一定的參考.

關(guān)鍵詞：Tate對(duì)；Eta對(duì)；Ate對(duì)；橢圓曲線；超橢圓曲線

0引言

雙線性對(duì)具有極高的安全性和很強(qiáng)的實(shí)用性，可用于構(gòu)造復(fù)雜、安全和高效的密碼協(xié)議.例如，雙線性對(duì)中的Weil對(duì)可用于構(gòu)造安全高效的簽名方案[1]；雙線性對(duì)中的Tate對(duì)可用于構(gòu)造多方密鑰管理方案[2-3]；將雙線性對(duì)與Diffie-Hellman結(jié)合，還可以用于構(gòu)造基于身份的加密方案[4].由于雙線性對(duì)的計(jì)算比較復(fù)雜，如何提高其運(yùn)算效率是關(guān)鍵問題.文獻(xiàn)[5]表明，Tate對(duì)的運(yùn)算效率高于Weil對(duì)，而Eta對(duì)和Ate對(duì)快于Tate對(duì).本文提出了基于Tate對(duì)，Eta對(duì)和Ate對(duì)代數(shù)曲線上的雙線性對(duì)算法，由于這3類曲線易于在軟件中實(shí)現(xiàn)，因此基于這3類曲線上的雙線性對(duì)算法具有一定的研究和應(yīng)用價(jià)值.

1雙線性對(duì)定義

1.1雙線性對(duì)

定義1雙線性對(duì)是如下形式的映射[6]：

e∶G×G→GT，

(1)

其中，G是一個(gè)加法群，GT是一個(gè)乘法群.

1.2Tate對(duì)

定義3設(shè)點(diǎn)P，Q為E上的點(diǎn)，fr,P是E上的有理函數(shù)，則Tate對(duì)定義如下：

er(P,Q)=fr,P(Q)(qk-1)/r.

(2)

定理1[7]設(shè)有正整數(shù)N，滿足N|qk-1且r|N，則有：

fr,P(Q)(qk-1)/r=fN,P(Q)(qk-1)/N.

(3)

1.3Eta對(duì)和Ate對(duì)

定義4設(shè)有正整數(shù)T，則Eta對(duì)定義如下：

ηT(P,Q)=fT,P(Q).

(4)

定理2[7]設(shè)E是域q上的超奇異橢圓曲線，k為嵌入次數(shù)，M=(qk-1)/N，φ是一個(gè)扭映射[8].如果存在整數(shù)a，c，L，使得T=q+cN，Ta+1=LN，則有：

(ηT(P,Q)M)aTa-1=(fN,P(Q)M)L.

(5)

e(P,Q)L=fT,P(Q)c(qk-1)/N，

(6)

2曲線y2+y=x3+x+b(b∈2)上的Tate對(duì)和Eta對(duì)實(shí)現(xiàn)

2.1曲線y2+y=x3+x+b(b∈2)上的Tate對(duì)實(shí)現(xiàn)

設(shè)E:y2+y=x3+x+b為域2n上的橢圓曲線，其中b∈2，n為奇數(shù).設(shè)P=(α,β)，Q=(x,y)為曲線E上的點(diǎn).由文獻(xiàn)[7]得嵌入次數(shù)k=4，令N=22n+1，則M=22n-1.

由文獻(xiàn)[7]得扭映射φ(x,y)=(x+s2,y+sx+t)，其中s,t滿足s2=s+1，t2=t+s.設(shè)映射φ(x,y)=(x+1,y+x)，則[2i]P=φi(α(2i),β(2i))，其中α(i)=α2i，β(i)=β2i.對(duì)i進(jìn)行分類討論可得：

設(shè)gi=h2iP(φ(Q))，把[2i]P代入h2iP可得gi，取n≡3(mod8)，由于s(i)=s+i，t(i)=t+is+τ(i)，其中i≡0,1(mod4)時(shí)，τ(i)=0；i≡2,3(mod4)時(shí)，τ(i)=1.則有：

2.2曲線y2+y=x3+x+b(b∈2)上的Eta對(duì)實(shí)現(xiàn)

由定理2可知，令T=q，N=22n+1，得c=0，a=2，L=1，代入式(5)可得：

令gi=h2iP(φ(Q))，由a,b∈2，x,y,α,β∈2n，及費(fèi)馬定理可得：

3曲線y2+y=x5+ax+b(a,b∈2)上的Tate對(duì)和Ate對(duì)實(shí)現(xiàn)

3.1曲線y2+y=x5+ax+b(a,b∈2)上的Tate對(duì)實(shí)現(xiàn)

設(shè)C∶y2+y=x5+ax+b為域2n上的超橢圓曲線，其中a,b∈2.則Jacobian群階為：(2n)=1±2(n+1)/2+2n±2(3n+1)/2+22n.

設(shè)hP為曲線C上的有理函數(shù)，由曲線C在P=(α,β)處的切線為y=(α4+a)(α+x)+β，得hP(x,y)=(α4+a)(α+x)+β+y，于是可得基于域2n上超橢圓曲線C的Tate對(duì)的值為：(φ(Q)))2(6n-i).

gi(6n-i)=(α(i+2)+a+d)(x(-i)+w(6n-i))+β(i)+Bα(i+1)+A+y(-i)+s2(6n-i)x(1-i)+s1(6n-i)x(-i)+s0(6n-i)+b.

3.2曲線y2+y=x5+ax+b(a,b∈2)上的Ate對(duì)實(shí)現(xiàn)

由定義5得(fT,P(Q)kqk-1)M=(fN,P(Q))ML，可令T=q，則N=212n-1，L=1，M=1，代入可得fT,P(Q)3×211n+2=fN,P(Q).由于T=q，可得基于域2n上曲線C的Ate對(duì)的值為：fT,P(φ(Q)(φ(Q)))2(n-i).設(shè)gi=h2iP(φ(Q))，由費(fèi)馬定理可得：

gi(n-i)=(α(i+2)+a+d)(x(-i)+w(n-i))+β(i)+Bα(i+1)+A+y(-i)+s2(n-i)x(1-i)+s1(n-i)x(-i)+s0(n-i)+b.

4曲線y2=xp-ax-b(a,b∈p)上的Ate對(duì)實(shí)現(xiàn)

設(shè)曲線Cp∶y2=xp-ax-b為域pn上的超橢圓曲線，其中p為奇素?cái)?shù)，a,b∈p，虧格g=(p-1)/2.由文獻(xiàn)[10]知嵌入次數(shù)k=p-1，可得N=p(p-1)n/2+1，M=p(p-1)n/2-1.設(shè)P=(α,β)，Q=(x,y)為曲線上的點(diǎn)，則基于域pn上曲線y2=xp-ax-b的Tate對(duì)的值為：fN,P(φ(Q).

設(shè)gi=hpiP(φ(Q))，p≡1(mod4)，由a,b∈p，x,y,α,β∈q，及費(fèi)馬定理可得.其中(-ab-b).將gi(n-i)代入fT,P(φ(Q))可得Ate對(duì)的值.

5結(jié)束語

本文研究了基于Tate對(duì)，Eta對(duì)和Ate對(duì)代數(shù)曲線上的雙線對(duì)，并通過公式化計(jì)算給出了具體的實(shí)現(xiàn)算法，為基于雙線性對(duì)密碼體制的研究和應(yīng)用提供了一定的參考.下一步工作將對(duì)其他特殊曲線上的雙線性對(duì)算法進(jìn)行研究.

參考文獻(xiàn)

[1]SHEN J, ZHENG W, WANG J, et al. An Efficient Verifiably Encrypted Signature from Weil Pairing[J]. Journal of Internet Technology, 2013, 14(6):947-952.

[2]CHANG S, KWON S, GAJ K. FPGA Accelerated Tate Pairing Based Cryptosystems over Binary Fields[C]//Field Programmable Technology, 2006. FPT 2006. IEEE International Conference on. IEEE, 2006:173-180.

[3]GALINDO D. Chosen-ciphertext secure identity-based encryption from computational bilinear Diffie-Hellman[M]//Pairing-Based Cryptography-Pairing 2010. Springer Berlin Heidelberg, 2010: 367-376.

[4]LE D P, TAN C H. Improved Miller’s algorithm for computing pairings on Edwards curves[J]. Computers, IEEE Transactions on, 2014, 63(10): 2626-2632.

[5]GALBRAITH S D. Supersingular curves in cryptography[M]//Advances in Cryptology—ASIACRYPT 2001. Springer Berlin Heidelberg, 2001: 495-513.

[6]CHEN C L, SHIH T F, TSAI Y T, et al. A Bilinear Pairing-Based Dynamic Key Management and Authentication for Wireless Sensor Networks[J]. Journal of Sensors, 2015：1-14.

[7]BARRETO P S L M, GALBRAITH S, HEIGEARTAIGH C O,et al. Efficient pairing computation on supersingular Abelian varieties[J].Designs,Codes and Cryptography, 2007,42(3):239-271.

[8]GALBRAITH S D, PUJOLs J, RITZENTHALER C, et al. Distortion maps for genus two curves[J]. Proceedings of A Workshop on Mathematical Problems & Techniques in Cryptology Crm, 2006, 3(1):46-58.

[9]楊怡琳.超橢圓曲線上快速標(biāo)量乘算法研究[D].杭州：杭州電子科技大學(xué),2014.

[10]施萬海,游林.一類超奇異超橢圓曲線的Tate對(duì)實(shí)現(xiàn)[J].杭州電子科技大學(xué)學(xué)報(bào),2013,33(6):33-36.

Bilinear Pairing Implementation Based on Three Type Algebraic Curves

NIAN Xiaoyu, YOU Lin

(InstituteofCryptographyandInformationSecurity,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

Abstract：In pairings, the most common is the Tate pairing, Eta pairing and Ate pairing are the variations of the Tate pairing. For the elliptic curve y2+y=x3+x+b where b∈2, the implementation algorithms of Tate pairing and Eta pairing in four cases are given by discussing respectively. Meanwhile, the implementation algorithms of Tate pairing and Ate pairing based on the hyperelliptic curve y2+y=x5+ax+b where a,b∈2 and the implementation algorithms of Ate pairing based on the hyperelliptic curve y2=xp-ax-b where a,b∈p are proposed. It provides a reference for the research and application of the pairing-based cryptosystem.

Key words：Tate pairing; Eta pairing; Ate pairing; elliptic curve; hyperelliptic curve

DOI：10.13954/j.cnki.hdu.2016.04.005

收稿日期：2015-12-18

基金項(xiàng)目：浙江省錢江人才計(jì)劃資助項(xiàng)目(2013R10071)

作者簡(jiǎn)介：年曉宇(1991-)，男，安徽蚌埠人，碩士研究生，密碼學(xué).通信作者：游林教授，E-mail：youlin@hdu.edu.cn.

中圖分類號(hào)：O153.4

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1001-9146(2016)04-0020-04