New version page

PAIRINGS ON HYPERELLIPTIC CURVES

Upgrade to remove ads

This preview shows page 1-2-14-15-30-31 out of 31 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

PAIRINGS ON HYPERELLIPTIC CURVESJENNIFER BALAKRISHNAN, JULIANA BELDING, SARAH CHISHOLM, KIRSTEN EISENTR¨AGER,KATHERINE E. STANGE, AND EDLYN TESKEDedicated to the memory of Isabelle D´ech`ene (1974-2009)Abstract. We assemble and reorganize the recent work in the area of hyperelliptic pairings: Wesurvey the research on constructing hyperelliptic curves suitable for pairing-based cryptography.We also showcase the hyperelliptic pairings proposed to date, and develop a unifying fra mework.We discuss the techniques used to optimize the pairing computation on hyperelliptic curves, andpresent many directions for further research.1. IntroductionNumerous cryptographic protocols for secure key exchange and digital signatures are based on thecomputational infeasibility of the discrete logarithm problem in the underlying group. Here, themost common groups in use are multiplicative groups of finite fields and groups of points on ellipticcurves over finite fields. Over the past years, many new and exciting cryptographic s chemes base don pairings have been suggested, including one-round three-way key establishment, identity-basedencryption, and short signatures [3, 4, 43, 64]. Originally, the Weil and Tate (-Lichtenbaum) pair-ings on supersingular elliptic curves were proposed for such applications, providing non-degeneratebilinear maps that are efficient to evaluate. Over time potentially more efficient pairings have beenfound, such as the eta [2], Ate [41] and R-ate [53] pairings. Computing any of these pairings involvesfinding functions with prescribed zeros and poles on the curve, and evaluating those functions atdivisors.As an alternative to elliptic curve groups, Koblitz [47] suggested Jacobians of hyperelliptic curves foruse in cryptography. In particular, hyperelliptic curves of low genus represent a competitive choice.In 2007, Galbraith, Hess and Vercauteren [29] summarized the research on hyperelliptic pairings todate and compared the efficiency of pairing computations on elliptic and hyperelliptic curves. Inthis rapidly moving area, there have been several new developments since their survey: First, newpairings have been developed for the elliptic case, including so-called optimal pairings by Vercauteren[71] and a framework for elliptic pairings by Hess [40]. Second, several constructions of ordinaryhyperelliptic curves suitable for pairing-based cryptography have been found [19, 22, 67, 20].In this paper, we survey• the constructions of hyperelliptic curves suitable for pairings, especially in the ordinary case,• the hyperelliptic pairings proposed to date, and• the techniques to optimize computations of hyperelliptic pairings.We alsoDate: September 22, 2009.Key words and phrases. Hyperelliptic curves, Tate pairing, Ate pairing.12 J. BALAKRISHNAN, J. BELDING, S. CHISHOLM, K. EISENTR¨AGER, K. STANGE, AND E. TESKEFigure 1. Classification of hyperelliptic pairingsHyperellipticpairings!!!!!!!!!!!!!!!!!!!!""""""""""""############WeilTateModifiedTateAtefamily$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$""""""""""""Eta(twistedonly)Ate(no finalexponent)Hess-Vercauteren(HV)%%%%%%%%%%%%AteiR-ate• give a unifying framework for hyperelliptic pairings which includes many of the recent vari-ations of the Ate pairing, and• present a host of potential further improvements.In this paper, we do not provide any comparative implementation, or give recommendations onwhich pairings should be used to satisfy certain user-determined criteria; this is left for future work.In our presentation, we focus on the case of genus 2 hyperelliptic curves and their Jacobians. Amongall curves of higher genus, such curves are of primary inte re st for cryptographic applications: Onthe one hand, we find explicit formulae along with various optimizations (e.g., [50, 73]), providingfor an arithmetic that is somewhat comp e titive with elliptic curve s. On the other hand, the securityis exactly the same as in the elliptic case, with the best attacks on the discrete logarithm problemin the Jacobian being square-root attacks based on the Pollard rho method (cf. [25]). However,Galbraith, Hess and Ve rcaute ren [29, §10.1] argue that pairing computations on hyperelliptic curveswill always be slow compared to elliptic curves: The most expensive part of a standard Tate pairingcomputation consists of repeatedly evaluating some function on a divisor and computing the productof the values obtained. Both in the elliptic and in the hyperelliptic case these divisors are definedover fields of the same size, but the functions in the hype re lliptic case are more complicated.Figure 1 represents the collection of hyperelliptic pairings at a glance. For use in pairing-basedapplications, originally the Weil and Tate pairings were proposed. The Weil pairing is much moreexpensive to compute than the Tate pairing, so it is not used in practice. The pairings in the Atefamily are potentially more efficient than the Tate pairing. Historically, the eta pairing was thefirst pairing to shorten the length of the Miller lo op. It is defined on supersingular c urves only andrequires a final exponentiation. It gave rise to the Ate pairings which are defined for all curves. Thehyperelliptic Ate pairing (which has a different definition than the elliptic Ate pairing !) has theadvantage that its loop length is roughly half of the length of the Miller loop for the Tate pairing. Italso is special in that it requires no final exponentiation (while the elliptic Ate pairing does requireone). Other variations of the Ate pairing include the Hess-Vercauteren (HV) pairings. These arethe pairings captured by our unifying framework, which generalizes work for the elliptic case byPAIRINGS ON HYPERELLIPTIC CURVES 3Hess [40] and Vercauteren [71]. HV pairings also have potentially shorter Miller loops than the Atepairing, depending on the embedding degree of the Jacobian. All of the HV pairings involve a finalexponentiation. Two examples of HV pairings are the R-ate and the Ateipairings. Table 5.6 inSection 5 gives more details about the diffe rences and merits of each pairing.Our paper is organized as follows. In Section 2 we review some of the background on Jacobians ofhyperelliptic curves. Section 3 discusses hyperelliptic curves of low embedding degree and what isknown about cons tructing them. Section 4 gives an overview of the different pairings on hyperellipticcurves following the classification in Figure 1. We also introduce the HV pairing framework, givea direct


Download PAIRINGS ON HYPERELLIPTIC CURVES
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view PAIRINGS ON HYPERELLIPTIC CURVES and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view PAIRINGS ON HYPERELLIPTIC CURVES 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?