Pairing computation on twisted Edwards form elliptic curves. (English) Zbl 1186.94433

Galbraith, Steven D. (ed.) et al., Pairing-based cryptography – Pairing 2008. Second international conference, Egham, UK, September 1–3, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85503-3/pbk). Lecture Notes in Computer Science 5209, 192-210 (2008).
Summary: A new form of elliptic curve was recently discovered by Edwards and their application to cryptography was developed by Bernstein and Lange. The form was later extended to the twisted Edwards form. For cryptographic applications, Bernstein and Lange pointed out several advantages of the Edwards form in comparison to the more well known Weierstraß form. We consider the problem of pairing computation over Edwards form curves. Using a birational equivalence between twisted Edwards and Weierstraß forms, we obtain a closed form expression for the Miller function computation.
Simplification of this computation is considered for a class of supersingular curves. As part of this simplification, we obtain a distortion map similar to that obtained for Weierstraß form curves by Barreto et al. and Galbraith et al. Finally, we present explicit formulae for combined doubling and Miller iteration and combined addition and Miller iteration using both inverted Edwards and projective Edwards coordinates. For the class of supersingular curves considered here, our pairing algorithm can be implemented without using any inversion.
For the entire collection see [Zbl 1155.94002].


94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11Y16 Number-theoretic algorithms; complexity


Full Text: DOI