Faster computation of the Tate pairing (Q2430985): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Changed an Item
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: Handbook of Elliptic and Hyperelliptic Curve Cryptography / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4409129 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficient implementation of pairing-based cryptosystems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Pairing-Friendly Elliptic Curves of Prime Order / rank
 
Normal rank
Property / cites work
 
Property / cites work: Twisted Edwards Curves / rank
 
Normal rank
Property / cites work
 
Property / cites work: Faster Addition and Doubling on Elliptic Curves / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficient Computation of Tate Pairing in Projective Coordinate over General Characteristic Fields / rank
 
Normal rank
Property / cites work
 
Property / cites work: Progress in cryptology -- INDOCRYPT 2008. 9th international conference on cryptology in India, Kharagpur, India, December 14--17, 2008. Proceedings / rank
 
Normal rank
Property / cites work
 
Property / cites work: Faster Pairing Computations on Curves with High-Degree Twists / rank
 
Normal rank
Property / cites work
 
Property / cites work: Pairing Computation on Twisted Edwards Form Elliptic Curves / rank
 
Normal rank
Property / cites work
 
Property / cites work: A normal form for elliptic curves / rank
 
Normal rank
Property / cites work
 
Property / cites work: A taxonomy of pairing-friendly elliptic curves / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5706769 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5571530 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ordinary Abelian varieties having small embedding degree / rank
 
Normal rank
Property / cites work
 
Property / cites work: Pairing-based cryptography -- Pairing 2008. Second international conference, Egham, UK, September 1--3, 2008. Proceedings / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3615887 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Another Approach to Pairing Computation in Edwards Coordinates / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5503704 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Advances in cryptology -- ASIACRYPT 2007. 13th international conference on the theory and application of cryptology and information security, Kuching, Malaysia, December 2-6, 2007. Proceedings / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Weil pairing, and its efficient calculation / rank
 
Normal rank
Property / cites work
 
Property / cites work: Public key cryptography -- PKC 2010. 13th international conference on practice and theory in public key cryptography, Paris, France, May 26--28, 2010. Proceedings / rank
 
Normal rank
Property / cites work
 
Property / cites work: Information security and cryptology -- ICISC 2004. 7th international conference, Seoul, Korea, December 2--3, 2004. Revised Selected Papers / rank
 
Normal rank
Property / cites work
 
Property / cites work: Advances in cryptology -- ASIACRYPT 2008. 14th international conference on the theory and application of cryptology and information security, Melbourne, Australia, December 7--11, 2008. Proceedings / rank
 
Normal rank
Property / cites work
 
Property / cites work: Selected areas in cryptography. 12th international workshop, SAC 2005, Kingston, ON, Canada, August 11--12, 2005. Revised selected papers. / rank
 
Normal rank
Property / cites work
 
Property / cites work: Pairing-based cryptography -- Pairing 2009. Third international conference Palo Alto, CA, USA, August 12--14, 2009. Proceedings / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3710637 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Progress in cryptology -- AFRICACRYPT 2008. First international conference on cryptology in Africa, Casablanca, Morocco, June 11--14, 2008. Proceedings / rank
 
Normal rank
Property / cites work
 
Property / cites work: Advances in cryptology - CRYPTO 2002. 22nd annual international cryptology conference, Santa Barbara, CA, USA, August 18--22, 2002. Proceedings / rank
 
Normal rank

Latest revision as of 22:44, 3 July 2024

scientific article
Language Label Description Also known as
English
Faster computation of the Tate pairing
scientific article

    Statements

    Faster computation of the Tate pairing (English)
    0 references
    0 references
    0 references
    0 references
    8 April 2011
    0 references
    The paper proposes some improvements in the computation of the Tate pairing on elliptic curves \(E\),\, both in Weierstrass form and in Edwards form, curves defined over a non-binary finite field \(F_q\)\, and with even embedding degree (for a prime \(n|\sharp(E)\)\, the embedding degree \(k\),\, with respect to \(n\),\, is the multiplicative degree of \(q\)\, modulo \(n\)). For \(E\)\, in Weierstrass form, Miller's algorithm computes efficiently the Tate pairing, using the chord-and-tangent method for the addition and doubling of points. Section 3 presents new formulas for the addition and doubling steps in Miller's algorithm. Those formulas use a representation of the points of \(E\)\, in Jacobian coordinates \((X:Y:Z:T)\), \(T^2=Z\), and the paper gives its cost in term of the costs \(m,s,M,S\) of multiplication and squaring in \(\mathbb F_q\) and \(\mathbb F_{q^k}\). A twisted Edwards curve, introduced by \textit{D. J. Bernstein} et al. [in: AFRICACRYPT 2008. Casablanca, Morocco, 2008. Lect. Notes Comput. Sci. 5023, 389--405 (2008; Zbl 1142.94332)], is a curve giving by an equation: \(E_{\text{ad}}: ax^2+y^2=1+dx^2y^2\), whose (affine) points have efficient addition formulas. Since the equation of \(E_{\text{ad}}\) has degree four the chord-and-tangent geometric interpretation of the addition is not more valid, but section 4 of the paper gives (theorem 2) a new geometric interpretation of the addition law for \(E_{\text{ad}}\), and with this tool section 5 shows how to compute Tate pairing on twisted Edwards curves. Section 6 gives the comparison of the proposed formulas with others in the literature, as the paper of \textit{S. Ionica} and \textit{A. Joux} [in: INDOCRYPT 2008. Kharagpur, India, 2008. Lect. Notes Comput. Sci. 5365, 400--413 (2008; Zbl 1203.94104)], concluding that `` ... our new formulas for Edwards curves solidly beat all previous formulas published for Tate computation on Edwards curves'' and `` Our new formulas for pairings on arbitrary Edwards curves are faster than all formulas previously known for Weierstrass curves except for the very special curves with \(a_4=0\).''. Finally, sections 7 and 8 present construction and numerical examples (with embedding degree \(k=6,8,10,22\)) of pairing-friendly Edwards curves, examples covering the most common security levels.
    0 references
    pairings
    0 references
    Miller functions
    0 references
    Weierstrass form
    0 references
    Edwards curves
    0 references
    doubling and addition formulas.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references