Arithmetic on abelian varieties and related topics 2014/03/03—Neuchâtel DamienR󰀻󰀮󰀱󰀾󰁀 ÉquipeLFANT,InriaBordeauxSud-Ouest February27,2014 Cryptography CurvesandJacobians Abelianvarieties Arithmetic Pairings Isogenies Isogenygraphs Discrete logarithm Definition(DLP) LetG =〈g〉beacyclicgroupofprimeorder.Letx(cid:0)(cid:78)andh=gx.The discretelogarithmlog (h)isx. g (cid:112) Exponentiation:O(logp).DLP:O(cid:101)( p)(inagenericgroup).Sowecan usetheDLPforpublickeycryptography. ⇒ Wewanttofindsecuregroupswithefficientadditionlawandcompact representation. Cryptography CurvesandJacobians Abelianvarieties Arithmetic Pairings Isogenies Isogenygraphs Elliptic curves Definition(chark(cid:54)=2,3) Anellipticcurveisaplanecurvewithequation y2=x3+ax+b 4a3+27b2(cid:54)=0. 2 R 1 Exponentiation: Q ((cid:96),P)(cid:55)→(cid:96)P P 0 -1.5 -1 -0.5 0 0.5 1 1.5 2 Discretelogarithm: -1 (P,(cid:96)P)(cid:55)→(cid:96) -R -2 Cryptography CurvesandJacobians Abelianvarieties Arithmetic Pairings Isogenies Isogenygraphs Scalar multiplication on an elliptic curve 3 2 1 P 0 2P -2 -1 0 1 2 3 -2P -1 -2 -3 -4 Cryptography CurvesandJacobians Abelianvarieties Arithmetic Pairings Isogenies Isogenygraphs Scalar multiplication on an elliptic curve 3 2 1 -3P P 0 2P -2 -1 0 1 2 3 -2P 3P -1 -2 -3 -4 Cryptography CurvesandJacobians Abelianvarieties Arithmetic Pairings Isogenies Isogenygraphs Scalar multiplication on an elliptic curve 3 2 1 -3P P 0 2P -2 -1 0 -5P 1 2 3 5P -2P 3P -1 -2 -3 -4 Cryptography CurvesandJacobians Abelianvarieties Arithmetic Pairings Isogenies Isogenygraphs ECC (Elliptic curve cryptography) Example(NIST-p-256) E ellipticcurvey2=x3−3x+ 41058363725152142129326129780047268409114441015993725554835256314039467401291over (cid:70) 115792089210356248762697446949407573530086143415290314195533631308867097853951 Publickey: P=(48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109), Q=(76028141830806192577282777898750452406210805147329580134802140726480409897389, 85583728422624684878257214555223946135008937421540868848199576276874939903729) Privatekey:(cid:96)suchthatQ=(cid:96)P. UsedbytheNSA; UsedinEuropeansbiometricpassports. Cryptography CurvesandJacobians Abelianvarieties Arithmetic Pairings Isogenies Isogenygraphs Pairing-based cryptography Definition Apairingisabilinearapplicatione :G ×G →G . 1 1 2 Example Ifthepairinge canbecomputedeasily,thedifficultyoftheDLPinG 1 reducestothedifficultyoftheDLPinG . 2 ⇒ MOVattacksonsupersingularellipticcurves. OnewaytripartiteDiffie–Hellman[Jou00]. Identity-basedcryptography[BF03]. Shortsignature[BLS04]. Self-blindablecredentialcertificates[Ver01]. Attributebasedcryptography[SW05]. Broadcastencryption[GPS+06]. Cryptography CurvesandJacobians Abelianvarieties Arithmetic Pairings Isogenies Isogenygraphs Jacobian of curves C asmoothirreducibleprojectivecurveofgenusg. Divisor:formalsumD=(cid:80)n P, P (cid:0)C(k). i i i degD=(cid:80)n . i Principaldivisor:(cid:80) v (f).P; f (cid:0)k(C). P(cid:0)C(k) P JacobianofC =Divisorsofdegree0moduloprincipaldivisors +Galoisaction =Abelianvarietyofdimensiong. DivisorclassofadivisorD(cid:0)Jac(C)isgenericallyrepresentedbyasum ofg points. Cryptography CurvesandJacobians Abelianvarieties Arithmetic Pairings Isogenies Isogenygraphs Example of Jacobians Dimension2:AdditionlawontheJacobianofanhyperellipticcurveof genus2: y2=f(x),degf =5. D=P1+P2−2∞ D′=Q1+Q2−2∞ b Q2 Q1 b b b b P2 b b P1b