Closed formulae for the Weil pairing inversion
type: Item
instance of: scholarly article
title: Closed formulae for the Weil pairing inversion
zbMATH Open document ID: 1175.11028
author: Takakazu Satoh
published in: Finite Fields and their Applications
publication date: 2008-08-27T00:00:00Z
review text: Pairings are bilinear maps \(\beta:\mathbb{G}_0\times\mathbb{G}_1\to\mathbb{G}_2\), with \(\mathbb{G}_0\), \(\mathbb{G}_1\), \(\mathbb{G}_2\) cyclic groups of the same order. Weil and Tate pairings are computed by the famous Miller's algorithm and some variants of it. In this paper, the following inversion problem is considered: \textit{Fixed pairing inversion} (FPI) Fixed \(x\in\mathbb{G}_0\), for any \(z\in\mathbb{G}_2\) find \(y\in\mathbb{G}_1\) such that \(\beta(x,y)=z\). Let \(E\) be an elliptic curve and let \(x\in E\) be an element of order \(m\in\mathbb{G}^+\). Let \(G=\langle x\rangle\) be the group generated by \(x\) in \(E\). Then, there is an elliptic curve, written commonly as \(E/G\), and an isogeny \(\phi:E\to E/G\) such that \(\text{ker}(\phi)=G\). The author is able to determine a map \(V_x:U_m\to (E/G)[m]\), where \(U_m\) is the multiplicative group of the \(m\)-th roots of unity, such that \(V_x\) is a monomorphism and whenever \(x\in (E/G)[m]\) but \(x\not\in\text{ker}(\widehat{\phi})\), where \(\widehat{\phi}\) is the dual isogeny, then for the Weil map \(W:E[m]\times E[m]\to U_m\)the following holds: \(\forall u\in U_m\;\left[W(x,V_{\widehat{\phi}(x)}(u)) = u\right].\) Thus \(V_{\widehat{\phi}(x)}\) is giving the solution to FPI. In section 4 the author provides some conditions restricting the values of \(V_a\) for general elliptic curves. But for the special cases of supersingular curves and field characteristic 2 and 3, the author gives explicit expressions for \(V_x\). Nevertheless, for practical purposes the full evaluation of these expressions is highly complex and the formal reduction obtained from the paper results remains hard.
reviewed by: Guillermo Morales Luna
Mathematics Subject Classification ID: 11G07
Mathematics Subject Classification ID: 11T71
zbMATH DE Number: 5316926
zbMATH Keywords: pairing inversion
zbMATH Keywords: Weil pairing
zbMATH Keywords: elliptic curves
MaRDI profile type: Publication
full work available at URL: j.ffa.2007.12.003
OpenAlex ID: W2051494591
cites work: The improbability that an elliptic curve has subexponential discrete log problem under the Menezes-Okamoto-Vanstone algorithm
cites work: Polynomial approximation of bilinear Diffie-Hellman maps
cites work: Q4265362
cites work: Advances in Cryptology - ASIACRYPT 2003
cites work: Q4496842
cites work: Hyperelliptic Pairings
cites work: Simplified pairing computation and security implications
cites work: A note on the Tate pairing of curves over finite fields
cites work: The Eta Pairing Revisited
cites work: On the Minimal Embedding Field
cites work: The Weil pairing and the Hilbert symbol
cites work: Q4737472
cites work: Interpolation of the discrete logarithm in \(\mathbb{F}_{q}\) by Boolean functions and by polynomials in several variables modulo a divisor of \(q-1\).
cites work: Elliptic curves with low embedding degree
cites work: The Weil pairing, and its efficient calculation
cites work: A polynomial representation for logarithms in GF(q)
cites work: A short proof for explicit formulas for discrete logarithms in finite fields
cites work: Coding and Cryptography
cites work: On Polynomial Interpolations related to Verheul Homomorphisms
cites work: Q3710637
cites work: Q5631239
cites work: Q2778850
cites work: Q5795562
cites work: A polynomial form for logarithms modulo a prime (Corresp.)
DOI: 10.1016/J.FFA.2007.12.003
description: scientific article; zbMATH DE number 5316926