Japan Advanced Institute of Science and Technology
https://dspace.jaist.ac.jp/
Title
Characterization of Elliptic Curve Traces under
FR-reduction
Author(s)
Miyaji, Atsuko; Nakabayashi, Masaki; Takano,
Shunzo
Citation
Lecture Notes in Computer Science, 2015/2001:
90-108
Issue Date
2001
Type
Journal Article
Text version
author
URL
http://hdl.handle.net/10119/4455
Rights
This is the author-created version of Springer,
Atsuko Miyaji, Masaki Nakabayashi, Shunzo Takano,
Lecture Notes in Computer Science, 2015/2001,
2001, 90-108.The original publication is
available at www.springerlink.com,
http://www.springerlink.com/content/rwm1prvmmvbav
gum
Description
Information security and cryptology - ICISC 2000
: third International Conference, Seoul, Korea,
December 8-9, 2000 : proceedings / Dongho Won
(ed.).
AtsukoMiyaji,MasakiNakabayashi,andShunzoTakano
JapanAdvancedInstituteofScienceandTechnology fmiyaji, [email protected]
Abstract. Ellipticcurvecryptosystems([19,25])arebasedonthe ellip-ticcurvediscretelogarithmproblem(ECDLP).Ifellipticcurve cryptosys-temsavoid FR-reduction([11,17]) andanomalousellipticcurve overFq ([34,3,36]),thenwithcurrentknowledgewecanconstructellipticcurve cryptosystemsovera smaller de nition eld. ECDLP has an interest-ing property that the security deeply depends on elliptic curve traces ratherthande nition elds,whichdoesnotoccurinthecaseofthe dis-cretelogarithmproblem(DLP).Thereforeitisimportanttocharacterize elliptic curve traces explicitly from the security point of view. As for FR-reduction,supersingular elliptic curvesor ellipticcurveE=Fq with trace2havebeenreportedtobevulnerable.Howeverunfortunatelythese havebeenonlyresultsthatcharacterizeellipticcurvetracesexplicitlyfor FR-orMOV-reductions.Moreimportantly,thesecuretraceagainst FR-reductionhas not beenreportedat all. Elliptic curveswiththe secure tracemeansthat thereducedextensiondegree is alwayshigherthana certainlevel.
In this paper, we aim at characterizing elliptic curve traces by FR-reductionandinvestigate explicitconditions oftraces vulnerableor se-cure againstFR-reduction. Weshownew explicit conditions of elliptic curvetraces for FR-reduction.We alsopresent algorithmstoconstruct suchellipticcurves,whichhaverelationtofamousnumbertheory prob-lems.
key words:ellipticcurvecryptosystems,trace,FR-reduction, numbertheory
1 Introduction
Koblitz and Miller proposed independently a public key cryptosystem based on an elliptic curveE de ned over a nite eld F
q
(q = p r
)([19,25]). If ellip-tic curvecryptosystems satisfy so called FR-conditions ([24,11,17]) and avoid anomalous elliptic curveoverF
q
([34,3,36]), then the only known attacks are thePollard-method ([27])andthePohlig-Hellmanmethod ([26]).Hence with currentknowledge,wecanconstructellipticcurvecryptosystemsoverasmaller de nition eldthanthediscretelogarithmproblem(DLP)-basedcryptosystems liketheElGamalcryptosystems([13])ortheDSA([12])andRSAcryptosystems
thesamesecurityasboththeElGamalcryptosystemsand RSAcryptosystems witha1,024-bitkey.
RecentlysomeresearchesoncomparingMOVandFR-reductionshavebeen reported in [15,18]. These attacks imbed a subgroup < G > E(F
q ) to F
q k for an extension eld F
q
k and reduce ECDLP based on < G > E(F q ) to DLP based on asubgroup of F q k , where G 2 E(F q
) is called a basepoint for ECDLP. MOV-reduction reduces ECDLP to DLP by using the Weil pairing ([35]). Supersingular elliptic curves([35]) havebeen reported to bevulnerable against MOV-reduction, which can be easily recognized by the trace t of the q
th
-power Frobenius endomorphism, t = q+1 #E(F q
): an elliptic curve is supersingular if and only if t 0 (modp). On the other hand, FR-reduction reduces ECDLP to DLP by using the Tate pairing. FR-reduction can attack elliptic curveswith trace2in additionto supersingular ellipticcurves.Infact, thesehavebeenonlyresultsthatcharacterizeellipticcurvetracesexplicitlyfrom a point of viewof FR- and MOV-reductions. It is interesting that in the case of E=F
p
overaprime eld,dangerous ellipticcurvetraceshappento be equal to 0(supersingular),1(anomalous)and2,whichcanbeeasilyrecognizedfrom otherellipticcurves.ThusECDLPhasaninterestingpropertythatthesecurity deeplydependsonellipticcurvetracesratherthande nition elds,whichdoes notoccurin the caseofDLP. Thereforeit isimportant to characterizeelliptic curvetracefrom thesecuritypointofview.
BalasubramanianandKoblitzinvestigatethatextensiondegreesrequiredto apply both reductions for ECDLP on G 2 E(F
q
) with order n are the same if n 6 jq 1([4]). Therefore without loss of generality we deal with only FR-reduction. By FR-reduction, ECDLP on G 2 E(F
q
) with order n is reduced to DLP onF q k ifand only ifnjq k
1.The probability that ellipticcurvesare vulnerableagainstFR-reduction,i.e.theextensiondegreekissmall,isshownto behighlyunlikely([4]):FR-reductionisconsiderednottobethreatinarealistic sense. Nevertheless all but supersingular and trace 2 elliptic curves have not beenprovedtobesecurein asense that theyarestrongagainstFR-reduction. Theremightexistanothertraceofellipticcurveswhichisreducedtoatmost6, seriouslylow, degreeextension eld, whose tracemightnotbesimplelike0or 2.Infact,supersingular ellipticcurveshaveratherspecialpropertiescompared withordinaryellipticcurves([35]),whichisthoughttocausesuchaweakfactor. Howeveralsoin the caseofordinaryelliptic curves,non-specialelliptic curves, theremightexistelliptic curvetraceswithaweakfactor.
More importantly, the secure trace against FR-reduction has not been re-portedyet.Ellipticcurveswiththesecuretracemeansthat thereduced exten-sion degreeisalwayshigherthan acertainlevel.This means that thesecurity of ECDLP over E=F
q
is guaranteed by the security of widely known DLP on F
q k
withhigherkthanacertainlevelsinceFR-reductiongivesanisomorphism betweenECDLP overE=F
q
and DLPbasedonasubgroupof F q k
([20]).In an-other light, the securetrace againstFR-reduction is usefulfor construction of ellipticcurvecryptosystems.Let'sconsiderthefollowingrequirements:itis
de-bechosenindependentlybyeachentityor byeachapplicationin orderto keep securityhigh([1]),andthatsuchaninitializationcouldbedonemoreeasilyover lowerCPU powerorsmaller memorylikea smartcard. Insuch requirements, it would be certainly desirable that an elliptic curve is constructable at least as easy as generating a prime number, which is adominant step of RSA-key generation([28]).Thisiswhyexplicitconditionsofsecureelliptic-curvetracesis usefulsincewecanconstructeasily anellipticcurvewithagivenspeci ctrace. ApparentlySEAalgorithm([30,32,7,10])isnotsuitablesinceitrequiresrather largememory.
Inthispaper,weaimatcharacterizingellipticcurvetracesbyFR-reduction and investigate explicit conditions of traces vulnerable or secure against FR-reduction.Here we summarizeourresultsonnewexplicit conditionsof elliptic curvetracesagainstFR-reduction.
LetE=F q
beanellipticcurvewithprime orderandthetracet. ÆECDLPonE=F q isreducedtoDLPonF q 3 byFR-reduction ,(i)(q;t) canberepresentedbyq=12l
2
1andt= 16l(l2Z),or (ii)(q;t)canberepresentedbyq=p
r
(r iseven)and t= p
q(i.e. supersin-gularellipticcurves).
ÆECDLPonE=F q isreducedtoDLPonF q 4 byFR-reduction ,(i)(q;t) canberepresentedbyq=l
2
+l+1andt= l;l+1(l2Z),or (ii)(q;t)canberepresentedbyq=2
r
(r isodd) andt= p
2q(i.e. supersin-gularellipticcurves).
ÆECDLPonE=F q isreducedtoDLPonF q 6 byFR-reduction ,(i)(q;t) canberepresentedbyq=4l
2
+1andt=12l(l2Z),or (ii) (q;t) canberepresentedbyq =3
r
andt= p
3q (r isodd) (i.e. supersin-gularellipticcurve).
Up to thepresent,it has not been reported whether there exist another ellip-tic curvetrace, except supersingular and trace2,reduced to at most 6-degree extension eld ornot. However,ourexplicitconditions meanthat prime-order ellipticcurvesarereducedtoatmost6-degreeextension eldifandonlyifthey satisfyatleastoneoftheaboveconditions.
LetECDLPonE(F q
)withthetracet bereducedtoDLPonF q k
. ÆIft3,thentheextensiondegreeksatis es
k
logq log(t 1)
";
where"isarealnumbersuchthat 1 10
>">0. ÆLett=3.Thentheextensiondegreeksatis es
k>logq ":
Thesesarethe rstexplicitelliptic-curve-traceconditionsonwhichreduced ex-tensiondegreesarealwayshigherthanacertainlevel.InthecaseofE=F ,
dan-gerouselliptic curvetraceshappento beequalto 0, 1and 2.Tothecontrary, ourresultshowsthat E=F
p
withtrace3issecureagainstFR-reduction. Furthermore,wepresentan algorithm to construct ellipticcurveswith the aboveconditionsandpresentsomeexamples.
This paper is organized as follows. Section 2 summarizes MOV- and FR-reductions.Section 3 investigates theabovenew explicitconditionsvulnerable orsecureagainstFR-reduction. Section4showsalgorithmstoconstructelliptic curveswithnewexplicitconditions.Section5presentssomeexamples.
2 MOV-reduction and FR-reduction
In this section, we summarize MOV- and FR-reductions against ECDLP on G 2 E(F
q
) with order n. Here the n-torsion subgroup is denoted by E[n] = fP 2E j nP=Og.
WecompareMOV-reductionwithFR-reduction.InMOV-reduction,ECDLP onGisreducedtoDLPforthesmallestintegerksuchthatE[n]E(F
q
k).Thus supersingularellipticcurvescanbeeÆcientlyreducedtoF
q k
fork6.Onthe other hand,in FR-reduction ECDLPon Gis reducedto DLPfor thesmallest integerksuchthatnjq
k 1.IfE[n]E(F q k),thennjq k 1([31]).Thereforesuch an elliptic curve vulnerable against MOV-reduction is also vulnerable against FR-reduction. In fact FR-reduction works also for elliptic curves with trace2 eÆcientlyin additiontosupersingularellipticcurves.
Table 1.KnownexplicitconditionsforFR-reduction
F q
(q=p r
) trace(E)extensiondegree p61(mod4)ifriseven 0 2 p61(mod3)ifriseven p q 3 p=2andrisodd p 2q 4 p=3andrisodd p 3q 6 riseven 2 p q 1 8q 2 1
BalasubramanianandKoblitz ([4]) showthat if nis aprimeand n6jq 1, then E[n] E(F q k) , n j q k 1:
As a result there is no di erence between MOV-reduction and FR-reduction exceptelliptic curveswithtrace2.Without lossof generality,wedealwiththe onlyFR-reductionin thispaper.
Table1summarizesknownexplicitconditionsofellipticcurvetracesfor FR-reduction,wheretheextensiondegreekmeansthatECDLPonE(F
q )isreduced toDLPonasubgroupofF k .
AsfortheprobabilitysuchthatECDLPisreducedtothelowerdegree exten-sion eldbyFR-reduction,BalasubramanianandKoblitzshowthenexttheorem. Theorem1 ([4]). Let (p;E) be a randomly chosen pair of a prime p in the interval M=2 p M and an elliptic curve E=F
p
with prime order n. The probability Prof njp
k
1for somek(logp) 2 satis es Pr<C (logM) 9 (loglogM) 2 M for C>0.
Theorem1saysthatFR-reductionishighlyunlikelytobeeÆcientattackagainst ECDLP. However we note that Theorem 1 does not describe whether there might exist another explicit criterion of an elliptic curve trace vulnerable or secureagainstFR-reduction ornot.FromTable1,wesee thatsuchanexplicit conditionthatgivestheextensiondegreehigherthanacertainlevelhasnotbeen reported.
3 New explicit conditions for elliptic curve traces
Inthissection,weinvestigatenewexplicitconditionsofellipticcurvetracesfor FR-reduction.Table2showsourresults,whichwillbediscussedinthefollowing sections.
Table 2.NewexplicitconditionsforFR-reduction
Fq(q=p r
)t=trace(E)extensiondegreek 12l 2 1 16l 3 l 2 +l+1 l ;l+1 4 4l 2 +1 12l 6 8q t3 k logq log(t 1) "
3.1 New explicit conditionsvulnerable against FR-reduction Inthis section, weinvestigate newconditionsof which ECDLP onE=F
q is re-ducedtoDLPonseriouslylowextension eldlikeF
q 3,F q 4,andF q 6,whichjust occurs in thecaseof supersingular ellipticcurves.Supersingular ellipticcurves haveratherspecialpropertiescomparedwithordinaryellipticcurves([35]),which wouldnodoubtcausesuchvulnerablefactor.Hereweshowthatthereexistalso vulnerableconditionsoftracesinthecaseofordinaryellipticcurves.
Let E=F q
be an elliptic curve with order n = #E(F q
) = q+1 t, where t is thetraceof E.Then weshowtheconditionsof whichECDLP onE=F
q is reducedtoDLPonF 3 byFR-reduction.
Theorem2. LetE=F q
beanellipticcurvewithprimeordern(q>64).ECDLP onE=F q isreducedtoDLPonF q 3
by FR-reductionifandonlyifoneofthe fol-lowing conditionsholds,
(i)(q;t)canberepresentedby q=12l 2
1andt= 16l (l2Z). (ii) (q;t) canbe representedby q =p
r
(r iseven) and t = p
q (i.e. super-singularelliptic curves).
proof:Weassumethat ECDLPonE=F q
withprime ordernisreducedtoDLP on F
q 3
by FR-reduction. From the condition of FR-reduction, n satis es that njq
3
1andn6jq 1sincenisaprime.Thereforethereisanintegersuchthat q 2 +q+1=n.Bysettingn=q+1 tandq 2 +q+1=(q+1) 2 t 2 +t 2 q, wegetthefollowingequation,
(q+1 t)(q+1+t )=q t 2
: (1)
ByHasse'sTheorem,thetracet satis esjtj2 p q.Hence,(1)satis es 3(1+ 1 q t q )(q+1+t )1: (2)
Forthe assumptionof q;t 2Zand q>64, weconcludethat (q;t) satis esone ofthefollowingequations,
q+1+t = 3; 2; 1;0;1 (3) Bysubstituting(3)to(1),wegetthat (q;t)satis es thefollowingequations,
t 2 +3t 4q 3=0; (4) t 2 +2t 3q 2=0; (5) t 2 +t 2q 1=0; (6) t 2 q=0; (7) t 2 t+1=0: (8)
Bysimplediscussionon theexistenceofintegersolutionsforcongruence equa-tions,wegetthat(t;q)2ZZexistsifand onlyif(t;q)satis es(5)or(7).
Inthecaseof(5),(t;q)isexpressedbyt= 16landq=12l 2
1forl2Z sinceq=p
r
foraprime p,andt2Zsatis es t= 1
p
3(q+1): In thecase of(7), (t;q) is expressed byt =
p q =
p p
r
for evenintegers r. Thisisjust asupersingularellipticcurve.
Conversely, ifaprime-orderellipticcurveE=F q
satis es(i)or (ii) in Theo-rem2,then#E(F
q
)=nsatis esnjq 3
1.ThereforeECDLPonE=F q isreduced to DLPonF q 3 .
Note that possibleorder of elliptic curvesis givenby Deuring([9])and Water-house([17]).InthecaseofE=F
p
,thereexactlyexistsanellipticcurveoftype(i) in Theorem2.InthecaseofF
2 r
,theredoesnotexistanyellipticcurveoftype (i)inTheorem2,butin thecaseofF
p r
Corollary 1 Let E=F q
be an elliptic curve with trace t. If (q;t) can be repre-sentedbyq=12l
2
1andt= 16l(l2Z),thenECDLPonE(F q )isreduced toDLPon F q 3 byFR-reduction.
proof:Hereweset#E(F q
)=nandletorderofG2E(F q
)bem.Thenmdivides n.Fromtheassumption,n=12l
2
6l+1.Thisyields12l 2
6l 1 (modn). Then byusing the relationof both 12l
2 6l 1 (modn)and q =12l 2 1, weget q 3 1=(12l 2 2)((12l 2 1) 2 +12l 2 ) (12l 2 2)((6l 2) 2 +(6l 1)) (modn) (12l 2 2)(36l 2 18l+3) (mod n) 0 (modn) 0 (modm):
Therefore ECDLP on 8 < G > E(F q ) is reduced to DLP on F q 3 by FR-reduction.
Nextweshowthe conditionsofwhichECDLP onE=F q isreducedto DLP onF q 4 byFR-reduction.
Theorem 3. LetE=F q
beanellipticcurvewithprimeordern(q>36).ECDLP on E=F q is reduced to DLP on F q 4
by FR-reduction if and only if one of the following conditionsholds,
(i)(q;t)canberepresentedby q=l 2
+l+1andt= l,l+1for l2Z. (ii)(q;t)canberepresentedbyq=2
r
(risodd)andt= p
2q(i.e.supersingular elliptic curves).
proof:Weassumethat ECDLPonE=F q
withprime ordernisreducedtoDLP on F
q 4
by FR-reduction. From the condition of FR-reduction, n satis es that njq
4
1andn6jq 2
1sincen isaprime.Thereforethere isanintegersuch thatq
2
+1=n.InthesamewayasTheorem2,wegetthefollowingequation,
(q+1 t)(q+1+t )=2q t 2
: (9)
FromHasse's Theorem,(9)satis esthat
2(1+ 1 q t q )(q+1+t )2: (10)
In the samediscussion asTheorem 2,weget that (t;q)2 ZZexists if and onlyif(t;q)satis es t 2 2q=0; (11) t 2 t q+1=0: (12)
Inthecaseof(11),tsatis est= p
2q= p
2p r
expressedbyt= l;l+1andq=l 2
+l+1forl2Zsincet2Zsatis es
t= 1 p 4q 3 2 :
Apparentlyifaprime-orderellipticcurveE=F q
satis es(i)or(ii)inTheorem3, thenECDLPonE=F
q isreducedtoDLPonF q 4 .
ThenextcorollaryfollowsfromTheorem3.
Corollary 2 Let E=F q
be an elliptic curve with trace t. If (q;t) can be repre-sentedby q=l
2
+l+1 andt= l, l+1for l2Z,then ECDLP on E(F q )is reducedtoDLPonF q 4 by FR-reduction.
In the same way as Theorems 2 and 3, the explicit conditions of which ECDLP on E=F q is reduced to DLP on F q 6
by FR-reduction are shown as follows.
Theorem4. LetE=F q
beanellipticcurvewithprimeordern.ECDLPonE=F q is reduced to DLP on F
q 6
by FR-reduction if and only if one of the following conditions holds,
(i)(q;t)canberepresentedby q=4l 2
+1andt=12l forl2Z. (ii) (q;t) canberepresentedby q=3
r
andt= p
3q for an odd integerr (i.e. supersingularelliptic curve).
Corollary 3 Let E=F q
be an elliptic curve with trace t. If (q;t) can be repre-sentedby q=4l
2
+1andt=12l for l2Z,thenECDLP on E=F q isreduced toDLPon F q 6 byFR-reduction.
Remark1 Theorems 2, 3, and4use the fact that the k-th cyclotomic polyno-mial is decomposed intoat most 2-degree irreducible polynomials over Zinthe case of k= 3, 4, and6, respectively. Forother cases of k,the same discussion might be usedif the k-th cyclotomic polynomial is decomposed into irreducible polynomials withrather smalldegrees overZ.
3.2 New explicit conditionssecureagainst FR-reduction
Inthissection,fromasecurepointofviewweinvestigateanewexplicitcondition of elliptic curvetraceson which the reducedextension degreeis alwayshigher thanacertainlevel.AsfortheknownresultsonE=F
p
,dangerousellipticcurves happentobesmalltraceslike0,1and 2.However,onthecontrary,ourresults ofTheorems2,3and4suggestthattheellipticcurvetracewhoseorderisnear upper bound in Hasse's Theorem([35]) should be vulnerable. As a result, we showthat theextension degreeis higherthanacertainlevelwhen thepositive
Theorem5. Let E=F q
be an elliptic curve with prime order n (q > 861), ECDLP onE(F q )bereducedtoDLPonF q k
,andt betheellipticcurvetrace.If t3,thenthe extensiondegreek satis es
k
logq log(t 1)
";
where" isareal numbersuchthat 1 10
>">0.
proof:ECDLPonE(F q )isreducedtoDLPonF q k ifandonlyif q k 1 (modn): (13)
By substituting n = q+1 t to (13), we get that k is the smallest integer satisfying
(t 1) k
1 (modn): (14)
Fromthe assumption and Hasse's theorem, t satis es 3t 2 p q q n. Therefore 1<(t 1) k <n<n+1 if 1 k< logn log (t 1)
. Then it follows that the smallestinteger k such that (t 1)
k
1 (modn)isgreaterthanorequalto logn log (t 1) .Furthermorebysubstituting n=q+1 t,wegetthat k logq log(t 1) "; where"= log t 1 (1 t 1 q
).Byusingtherelationof3t2 p q,wegeteasily that 0<"< log t 1 (1 2 p q + 1 q )< 1 10 ;
ifq>861.Apparentlythelargerqis,thesmaller"is.Thusthelowerbound of extensiondegreeisgivenby
k
logq log(t 1)
":
Theabovetheoremgivesalowerboundofextensiondegreekinthecaseofsmall t3,whichensuresthesecurityofECDLPoverE=F
q
bythatofwidelyknown DLPonF
q k
Corollary 4 Let E=F q
be an prime order elliptic curve with t =3 (q > 861) and ECDLP on E(F
q
) bereducedto DLPon F q k
. Then the extension degree k satis es
k>logq "; where" isareal numbersuchthat
1 10
>">0.
Remark2 The extension degree k < logq means that FR-reduction gives a subexponentialattackagainstECDLPundertheindexcalculusmethod([8]),which runsoverany eldF
q intimeL q [1=2;c]=exp((c+O(1))(logq) 1=2 (loglogq) 1=2 ). On the other hand, the extension degree k <(logq)
2
means that FR-reduction gives asubexponentialattackagainst ECDLPunder thenumber eldsieve([14]) which runsoversome eldsF
q intime L q [1=3;c]=exp((c+O(1))(logq) 1=3 (loglogq) 2=3 ):
Therefore in order to construct enough secure elliptic curve cryptosystems it wouldbedesirablethatk(logq)
2
.Howevertheconditionofklogqin Corol-lary4isnothighly optimisticif weestimate underaratherrealistic assumption ofthe discretelogarithmalgorithmfor de nition eldsofelliptic curves([29,8]). Inthecaseofprime-orderellipticcurvesE=F
p
witht=3,wewilleasilyseethat thefollowingstrictconditionalsoholds:theextensiondegreeisjustexponential. Corollary 5 LetE=F
p
beaprime-orderellipticcurvewitht=3(i.e.#E(F p
)= p 2isprime).If2isaprimitive rootinF
p 2
,thentheextensiondegreeksuch that ECDLP onE(F
p )isreducedtoDLP onF p k satis esk=p 3. 4 Algorithm
Inthissection,wedescribealgorithmstoconstructellipticcurvesvulnerableor secure againstFR-reduction in Section 3and con rm that such elliptic curves existinarealisticsense(i.e.constructable).Fromthepointofviewoftheoretical interest,eachconstructionisdeeplyrelatedtoeachfamousnumbertheory prob-lem:theformerisaproblemof ndingintegersolutionsofPell'sequation([16]), andthelatterisaproblemof ndingtwinprimenumbers.
4.1 Construction of elliptic curves reducible to lower extension degree
Herewepresentanalgorithmto constructellipticcurvesoverF p
inCorollary1 sinceTheorem2isaspecialcaseofCorollary1.ByusingtheCM-method([2])
1 , 1
The procedure of the CM-method includes a step of computing the Hilbert class polynomials([23]),P
d
(x).ThecomputationoftheHilbertclasspolynomialsarenot so easyifthe degreeof theHilbert classpolynomial,deg(Pd(x)),namelytheclass numberis large. Therefore we usually x d and so P
d
(x) beforehand in order to avoidthe computationof Pd(x)aswe willseeinAlgorithm2.Inanother way,we maymakeuseoftherecentresearches([5,6])ontheconstructionoftheCMelliptic
thedominantstepofconstructionofellipticcurveswithbothp=12l 2
1and t= 16l(l2Z)is ndingintegersolutions(l;y)of 12l
2
12l 5=dy 2
for agivenpositiveintegerd3 (mod4), which iseasilytransformedinto nding integersolutionsofanindeterminateequation
x 2
3dy 2
=24: (15)
Fromtheelementarynumbertheory([37]), allintegersolutions(x;y)of (15)is givenby x+y p 3d=(x 1 +y 1 p 3d)(t 0 +u 0 p 3d) n ; where (t 0 ;u 0
)is theminimum positive integer solutionon =t 0 +u 0 p 3d >0 ofPell'sequation, T 2 3dU 2 =1; (16) and(x 1 ;y 1
)isanintegersolutionof(15)inthefollowingdomainDom, Dom=f(x;y)j p 24x<t 0 p 24 ;0x<u 0 p 24 g: Herewecalltwointegersolutions(x;y)and(x 0 ;y 0 )of(15)areassociatedif x+y p 3d=(x 0 +y 0 p 3d)(t 0 +u 0 p 3d) n for9n2f0;1;2;g.
After nding aninteger solution (x;y) of (15) in the aboveprocedure,the construction of elliptic curves E=F
p
with the trace t easily follows the CM-method. Inorder to nd integersolutions eÆciently, we needsome techniques speci cto(15).Hereweshowonlyspeci ctechniques,allofwhichareprovedby simplediscussionontheexistenceofintegersolutionsforcongruenceequations.
Lemma1. Ifthereexistsanintegersolution(l;y)of12l 2 12l 5=dy 2 ,then d19 (mod24). proof:Fromdy 2 =12l 2 12l 5=12l(l1) 519 (mod24),wegetdy 2 19 (mod 24).Byusingthefactofy
2
0;1;4;9;12;16 (mod24),wegetthatd19 (mod 24)ifthereexists anintegersolutionofdy
2
19 (mod 24).
Lemma2. Let d 2Z be d 19 (mod24). If there exists an integer solution (x 0 ;y 0 )of (15),thengcd (x 0 ;y 0 )=1.
proof:Let(x;y)beanintegersolutionof(15)andgcd(x;y)=g>1.Theng=2 sinceg 2 j24. Sowecanset x=2x 0 andy =2y 0 (x 0 ;y 0 2Z)withgcd(x 0 ;y 0 )=1. From the assumption of d 19 (mod 24), (x
0 ;y 0 ) satis es x 0 2 +3y 0 2 6 (mod 12). This is contradictory because there does not exist any integer so-lution(x;y)ofx
2 +3y
2
Corollary 6 Let d2Zbed19 (mod24). If there existsan integer solution (x 0 ;y 0 )of (15),thenboth x 0 and y 0 areodd.
proof:Thisfollowsfrom Lemma2.
Lemma3. Let d 2 Z be d 19 (mod24) and (x 0
;y 0
) be a set of integer solutions of(15). Then both(x
0 ;y 0 )and(x 0 ; y 0
)arenot associated.
proof: Two solutions (x;y) and (x 0
;y 0
) of (15) are associated if and only if xy
0 x
0
y 0 (mod24)(see Section 34in [37]). Thereforeif both (x 0 ;y 0 ) and (x 0 ; y 0
) are associated, then 2x 0
y 0
0 (mod24). This is contradictory to Corollary6.
Lemma4. Letd2Zbed19 (mod 24). Then thereare atmost twointeger solutions inDom for(15).
proof:FromLemma 2,thereexist anintegersolutions satisfyingthefollowing conditions: 12d=s 2 96m,gcd(24;s;m)=1,s 2 12d (mod 96),and 24s<24, ifthere exist anintegersolution(x;y)in Dom for(15)(see Section35 in [37]). Fromthesimplediscussionontheexistenceofintegersolutionsforcongruence equations,there areat mosttwointegersolutionss satisfyingtheabove condi-tions.ThereforethereareatmosttwointegersolutionsinDomfor(15). ThenextpropositionfollowsfromLemmas 3and4.
Proposition1 Letd2Zbed19 (mod24).Then thereexistjusttwosetsof integer solutionsin Dom for (15) ifthere exist.
Herewegivethealgorithmasfollows:
Algorithm1 Given the upper bound UP >0 on a prime p, this algorithm outputs (p;d;l), or fail if such a (p;d;l) does not exist.
1. Choose a positive integer d such that d19 (mod24). 2. Find the minimum positive integer solution (t
0 ;u
0
) of (16). 3. Find an integer solution (x;y)2Dom of (15), if exists.
Otherwise, output fail and terminate the algorithm. 4. For n1, set x
n , y
n
in such a way that x n +y n p 3d:=(x+y p 3d)(t 0 +u 0 p 3d) n . 5. Set l 1;n :=(x n 3)=6, l 2;n :=(x n +3)=6, p 1;n :=12l 2 1;n 1, and p 2;n =12l 2 2;n 1. 6. If p 1;n >UP and p 2;n
>UP, then output fail and terminate the algorithm.
7. If p 1;n
or p 2;n
is prime, then output (p 1;n ;d;l 1;n ) or (p 1;n ;d;l 2;n ) respectively, and terminate the algorithm. Otherwise goto 4.
4.2 Construction of elliptic curves reducible to higherextension degree
Here we present an algorithm to construct elliptic curvesE=F p
with t = 3in Corollary4,inwhichtheCM-methodisalsousedinthesamewayasSection4.1. By using the CM-method, the dominant steps of construction of prime-order elliptic curves E=F
p
with t = 3,namely #E(F p
) =p 2,are nding aprime numberp=dl
2 +dl+
d+9 4
withl2Zforangivenpositiveintegerd3 (mod4), andcheckingp 2isalsoprime.
Inthiscasewecaneasily showthefollowingconditionofd.
Lemma5. Let p 2 Z be p = dl 2
+dl + d+9
4
with a positive integer d 3 (mod 4).Ifbothpandp 2areprime, thend19 (mod 24).
proof:Fortheassumption ofd3 (mod 4),weset d=3+4m(m2Z).Then
p=dl 2 +dl+ d+9 4 =dl(l+1)+(m+3) (17) m+1 (mod2): (18)
Sincepisprime,m0 (mod 2)from(18).Sowecansetd=3+8m 0
(9m 0
2Z). Ontheotherhand,wegetp1 (mod 6)sincebothpandp 2areprime and alsoget easilyl(l+1)0; 2 (mod6) for8l2Z.Ifl(l+1)0 (mod6), then m
0
2 (mod3)from(17).Thisyieldsd19 (mod24).Ifl(l+1)2 (mod6), thenthisyieldscontradictory.Inthiswaywegetd19 (mod24).
Herewegivethealgorithmasfollows:
Algorithm2 Given the upper bound UP >0 on a prime p, this algorithm outputs the prime-order elliptic curve E=F
p
with t=3, or fail if such an E=F
p
does not exist.
1. Choose a positive integer d such that d19 (mod24). 2. Set p=dl(l+1)+
d+9 4
for Z3l>0 such that l0;2 (mod3). 3. If p>UP, then output fail and terminate the algorithm.
Otherwise goto step 4.
4. If both p and p 2 are prime, then goto step 5. Otherwise goto step 2 and try the next l.
5. Compute the Hilbert class polynomial P d (x). 6. Solve a root j 0 of P d (x)0 (modp). 7. Construct two elliptic curves E
j0 and E 0 j 0 , E j0 :y 2 =x 3 +a j0 x+b j0 , E 0 j 0 :y 2 =x 3 +a j0 c 2 x+b j0 c 3 ; where a j0 = 3j0 1728 j0 (mod p), b j0 = 2j0 1728 j0 (modp), and c is any quadratic non-residue in F
p . 8. Output E2fE j0 ;E 0 j0 g with #E(F p )=p 2 and terminate the algorithm.
Notethatthestep8canbeperformedeasily:outputE suchthat(p 2)G=O forE(F )39G6=O.
5 Experimental results
Inthissection,wepresentsomeexamplesinbothvulnerableandsecurecases.
5.1 Ellipticcurves reducibleto lowerextension degree
Wepresentoneexamplewhichsatis estheconditionofCorollary1.Wesearched elliptic curves E=F
p
in the range of0 <p<2 1000
by using Algorithm 1.Our moduloarithmeticusestheGNUMPLibraryGMP([38]).Theplatformisan Al-pha21264(500MHz/CCompilerforDigitalUNIX).Ittookontheaverage0.101 secto ndanellipticcurveE=F
p
inthecaseofd=19.Wehavealsocon rmed experimentallythat vulnerableelliptic curveswith new explicit conditionsare constructablesystematicallyinthesamewayassupersingularortrace2elliptic curves.This means that even in the case of ordinary elliptic curves,we must checkFR-conditions.
Recentlysomeresearches([21,22])onaprotocolusinganellipticcurveE=F p withthecomputableFR-reductionhavebeenproposed,inwhichanellipticcurve E=F
p
reducedtoF p
k withthecomputablelowerextensiondegreeisdesired.Our approachisalsodeeplyrelatedto theirresearches.
Example1 E=Fp :x 3 +ax+b p=90876100379 0427908077 5489557583 8035667582 9026531247 (170-bit), a=818416 3425948882 9148504408 8811640789 0530857899 75506, b=66607044332 3978349780 0358818034 1328286571 4842057992, t= 52213820118 5402993899 01413, #E(Fp)=7 2 313n, n=5925285 2825873893 7261230363 1558978126 2054405453 (156-bit).
5.2 Ellipticcurves reducibleto higherextension degree
Wepresentexperimental resultsandsomeexamplesofellipticcurvesin Corol-laries 4and 5.Wehavecon rmed that secureelliptic curveswith newexplicit conditions areconstructible systematically. Table 3shows numericalresults of twinprimes(p;p 2) withp=dl
2 +dl+
d+9 4
, whichwassearchedin therange of2 76 2 20 l2 76 +2 20
.Ourmoduloarithmetic usestheGNUMPLibrary GMP([38]). Theplatform is an Alpha 21264(500 MHz/C Compilerfor Digital UNIX).Ittookontheaverage0.053secto ndapairof(p;p 2)inthecaseof d=163.Forothercasesofd,wecould ndsuchapairofprimesontheaverage 0.064 1.402 sec. Fig.1 shows the plot of Table 3 from the point of view of deg(P
d
(x)) and thesize of d onP d
(x). Fromour experimental result, wehave foundaheuristicpropertythatthenumberoftwinprimesarecloselyrelatedto twofactors,deg(P
d
(x))and thesize ofdonP d
(x). Ifwe x thesize ofd, then the larger deg(P
d
(x)) is, the less twin primes are found. If we x deg(P d
(x)), thenthelargerthesizeofdis,themoretwinprimesarefound.s
twin-prime-Table3.Thenumberoftwinprimes(p;p 2)
ddeg(P d
(x)) #twinprimes times(sec)
19 1 190 0.550 43 1 1,157 0.094 67 1 1,902 0.064 91 2 450 0.365 115 2 1,036 0.209 139 3 139 0.323 163 1 5,158 0.053 187 2 1,402 0.107 211 3 292 1.401 235 2 2,523 0.089 259 4 247 0.348 283 3 645 0.234 307 3 696 0.134 331 3 1,458 0.103 355 4 635 0.261 379 3 1,583 0.074 403 2 3,392 0.069 p=dl 2 +dl+ d+9 4 (2 76 2 20 l2 76 +220 )
samesecuritylevel,weconsiderthefollowingthreeconditionsofbit sizeon (el-lipticcurvecryptosystem,RSA):(160,1024),(224,2,048)and(256,3,072)([33]). Table4showsboth of twin-prime-generationtimes and RSA-prime-generation times,wherethesizeofRSA-primeisjusthalfsizeoftheabovesecuritylevel.As forthetwin-primegeneration,wedealtwithfourcasesofd=163;427;907;1555 thatcorrespondto deg(P
d
(x))=1,2,3,4respectively.Thesecharactersarealso used in Table4and Fig 2. Wesearchedfor 1,000 twin primes by Algorithm2 andcomputedtheaveragetimes.AsfortheRSA-primegeneration,wesearched for 1,000 RSA primes by simply performing aprimality test among odd num-bers,andcomputedtheaveragetimes.TheplatformisalsoanAlpha21264(500 MHz /C compiler for Digital UNIX). Forthe primality test, we made use of Miller-Rabin'sprobablistictestinGNUMPLibraryGMP.Fig2showstheplot ofTable4.Notethattheverticalaxisisrepresentedinlogarithm.Wecaneasily seethat thegenerationoftwinprimesisfasterthanthat ofRSAprimesin any case. WepresentE=F p :y 2 =x 3
+ax+bwitht=3inthefollowing.InExamples2 4,2isaprimitiverootin F p 2 . Example2 E1=Fp:y 2 =x 3 +a1x+b1,(jpj=159 bit) p=5195181601449 6938238659 2375449686 0216304833 66071, n=5195181601449 6938238659 2375449686 02163 0483366069, a 1 =3529380 8281903345 1679859515 2174757876 81700632697, b1=4084647752610 1209524877 0468628212 5323312948 77155,
Fig.1.Relationsbetween#twinprimesandPd(x) Example3 E 1 =F p :y 2 =x 3 +a 1 x+b 1 ,(jpj=159 bit) p=7935497171445 1367192705 0677226939 8345880422 30471, n=7935497171445 1367192705 0677226939 83458 8042230469, a1=62232433 7578136504 3814580347 5670857012 7320393428, b1=6793994641002 6222689665 5582246785 6582808943 39109, Example4 E=F p :y 2 =x 3 +ax+b,(jpj=240 bit) p= 112 49846 54526 86189 73518 65205 55113 42541 99281 27068 83806 23265 87119 5502307023, n= 112 49846 54526 86189 73518 65205 55113 42541 99281 27068 83806 23265 87119 5502307021, a = 52 37381 80880 77183 56601 62811 25609 08710 91667 71974 15904 90057 09224 6937760775, b = 34 91587 87253 84789 04401 08540 83739 39140 61111 81316 10603 26704 72816 4625173850. Example5 E 1 =F p :y 2 =x 3 +a 1 x+b 1 ,(jpj=240 bit)
Table 4.Timesoftwin-primegenerationandRSA-primegeneration(sec)
bitsize(twin primes,RSA) (160,1024)(224,2048)(256,3072) RSA 0.098 0.826 16.274 1 0.047 0.130 0.242 Twinprimes 2 0.058 0.164 0.265 3 0.057 0.274 0.401 4 0.057 0.175 0.272
Fig.2.Timesoftwin-primegenerationandRSA-primegeneration p= 145 62684 79172 80895 91487 33486 94032 72646 08218 46342 12380 03553 12226 4354852871, n= 145 62684 79172 80895 91487 33486 94032 72646 08218 46342 12380 03553 12226 4354852869, a 1 =14444371 02824 33267 37769 11780 11326 91187 09134 83450 79361 18648 91066 4337785210, b1 = 5011979 94855 57136 68786 73438 08285 32827 34850 99302 48151 81056 65622 1474374505, 6 Conclusion
Inthispaper,wehaveshownsomenewexplicitconditionsofellipticcurvetraces vulnerable or secure againstFR-reduction. Wehavealso presented algorithms toconstructellipticcurveswithournewexplicitconditions.Especiallyournew secure elliptic curverealizes rather light initialization, which sets upa pair of ellipticcurveandbasepoint.
Acknowledgments
Theauthorsaregratefultoanonymousrefereesforinvaluablecomments.
References
1. R. Andersonand R.Needham, \Robustnessprinciplesfor publickey protocols", Advancesin Cryptology-Proceedings of CRYPTO'95, LectureNotesinComputer
2. A. O.L. Atkinand F.Morain,\Ellipticcurvesandprimality proving", Math. of Computation,61(1993),29-68.
3. K. Arakiand T.Satoh\Fermat quotients and the polynomialtime discrete log algorithmforanomalousellipticcurves",CommentariiMath.Univ.St.Pauli.,vol. 47(1998),81-92.
4. R.Balasubramanian andN. Koblitz,\TheImprobability ThatanEllipticCurve HasSubexponentialDiscreteLogProblemundertheMenezes-Okamoto-Vanstone Algorithm",J.Cryptology,11(1998),141-145.
5. J.Chao,O.Nakamura,K.Sobataka,andS.Tsujii,\Constructionofsecureelliptic curveswith CM tests and lifting", Advances in Cryptology-Proceedings of ASI-ACRYPT'98, LectureNotes inComputer Science,1514(1998), Springer-Verlag, 95-109.
6. J.Chao, M. Hosoya,K.Sobataka,andS.Tsujii,"Constructionof Elliptic Cryp-tosystems Using OrdinaryLifting", Proceeding of the1999 Symposium on Cryp-tographyandInformationSecurity,163-166.
7. J. M. Couveignesand F. Morain, \Schoof's algorithm and isogeny cycles", Pro-ceedingsoftheANTS-I,LectureNotesinComputeScience,877(1994), Springer-Verlag,43-58.
8. T.Denny,O.SchirokauerandD.Weber,"Discretelogarithms:thee ectivenessof theindexcalculusmethod",ProceedingsofANTSII,LectureNotesinComputer Science,1122(1996),Springer-Verlag,337-361.
9. M. Deuring, \Die typen der multiplikatorenringe elliptischer funktionenkorper", Abh.Math.Sem.Hamburg,14(1941),197-272.
10. N.D.Elkies,\Explicitisogenies",Preprint,1991
11. G.FreyandH.G.Ruck,\Aremarkconcerningm-divisibilityandthediscrete loga-rithminthedivisorclassgroupofcurves",Mathematicsofcomputation,62(1994), 865-874.
12. \Proposedfederal informationprocessing standardfor digitalsignature standard (DSS)",FederalRegister,56No.169,30Aug1991,42980{42982.
13. T.ElGamal,\Apublickeycryptosystemandasignatureschemebasedondiscrete logarithms", IEEETrans.Inform.Theory,IT-31(1985),469{472.
14. D.M.Gordon,\DiscretelogarithmsinGF(p)usingthenumber eldsieve",SIAM J.onDiscrete Math.,6(1993),124-138.
15. R. Harasawa,H.Imai, J.Shikata,J.Suzuki, \ComparingtheMOV and FR Re-ductionsinEllipticCurveCryptography",Advances inCryptology-Proceedings of EUROCRYPT'99,LecturenotesinComputerScience,1592(1999),190-205. 16. K.IrelandandM.Rosen,Aclassicalintroductiontomodernnumbertheory,GTM
84,Springer-Verlag,New-York,1982. 17. IEEE P1363Working Draft,June16,1998.
18. N. Kanayama, T. Kobayashi, T. Saito, and S. Uchiyama "Remarks on elliptic curve discrete logarithm problems" , IEICE Trans., Fundamentals. vol. E83-A, No.1(2000),17-23.
19. N. Koblitz, \Elliptic curve cryptosystems", Mathematics of Computation, 48 (1987),203{209.
20. N. Koblitz, \Anellipticcurve implementationofthe nite eld digitalsignature algotirhm",AdvancesinCryptology-Proceedings ofCRYPTO'98,LectureNotesin ComputerScience,1462(1998),Springer-Verlag,327-337.
22. M. Kasahara, K.Ohgishi, and R. Sakai"Cryptosystems based onpairing", The 2000SymposiumonCryptographyandInformationSecurity,SCIS2000-C20,Jan. 2000.
23. S.Lang,EllipticFunctions, GTM112,Springer-Verlag,NewYork,1987.
24. A.Menezes,T.OkamotoandS.Vanstone,\Reducingellipticcurvelogarithmsto logarithmsina nite eld",Proceedingsofthe 22ndAnnual ACMSymposiumon theTheoryof Computing(1991),80{89.
25. V. S. Miller, \Use of elliptic curves in cryptography", Advances in Cryptology-Proceedings of Crypto'85, Lecture Notes in Computer Science, 218 (1986), Springer-Verlag,417-426.
26. S.C.PohligandM.E.Hellman,\Animprovedalgorithmforcomputinglogarithms overGF(p)anditscryptographicsigni cance", IEEE Trans. Inf.Theory, IT-24 (1978),106{110.
27. J.Pollard,\MonteCarlomethodsforindexcomputation(modp)",Mathematics of Computation,32(1978),918{924.
28. R.Rivest,A.ShamirandL.Adleman,\Amethodforobtainingdigitalsignatures and public-keycryptosystems", Communications of the ACM, 21 No. 2 (1978), 120{126.
29. T.SaitohandS.Uchiyama,"ANoteontheDiscreteLogarithmProblemonElliptic CurvesofTraceTwo",TechnicalReport ofIEICE,ISEC98-27(1998),51-57. 30. R. Schoof, \Elliptic Curves Over Finite Fields and the Computation of Square
Rootsmodp",Mathematicsofcomputation,44(1985),483{494.
31. R.Schoof,\Nonsingularplanecubiccurvesover nite elds",Jornalof Combina-tionTheory, vol.A.46(1987),183-211.
32. R.Schoof,\Countingpointsonellipticcurveover nite elds",JournaldeTheorie desNombresde Bordeux,7(1995),219{254.
33. StandardsforEÆcientCryptographyGroup.http://www.secg.org/
34. I.A.Semaev\Evaluationofdiscretelogarithmsinagroupofp-torsionpointsofan ellipticcurveincharacteristicp",Mathematicsofcomputation,67(1998),353-356. 35. J. H. Silverman,The Arithmetic of Elliptic Curves, GTM 106,Springer-Verlag,
NewYork,1986.
36. N. P.Smart \Thediscretelogarithm problemonellipticcurvesof traceone", J. Cryptology,12(1999),193{196.
37. T.Takagi,Syotou seisuuronnkougi,KyourituSyuppan,1971,(inJapanese). 38. Torbjorn Granlund, THE GNU MP LIBRARY, version 3.1, August 2000.
