Point compression for the trace zero subgroup over a small degree extension field
The article is devoted to the study of the trace zero variety of an elliptic curve defined over the finite field \(\mathbb{F}_q\) of \(q\) elements. More precisely, a description of the \(\mathbb{F}_q\)-rational points of the trace zero variety of a given elliptic curve is obtained, a new representation of these points is proposed, and an algorithm for compression and decompression is described and analyzed. Let \(E\) be an elliptic curve defined over \(\mathbb{F}_q\). For a field extension \(\mathbb{F}_q|\mathbb{F}_{q^n}\), denote by \(E(\mathbb{F}_{q^n})\) the group of \(\mathbb{F}_{q^n}\)-rational points of \(E\). The kernel of the trace map \(\varphi:E(\mathbb{F}_{q^n})\to E(\mathbb{F}_q)\) is the \textit{trace zero subgroup} \(T_n\) of \(E(\mathbb{F}_{q^n})\). By Weil restriction the points of \(T_n\) can be viewed as the \(\mathbb{F}_q\)-rational points of an abelian variety \(V\) of dimension \(n-1\) defined over \(\mathbb{F}_q\), which is called the \textit{trace zero variety}. In the paper under review, a new representation for the elements of \(T_n\) is discussed. Choosing a basis of \(\mathbb{F}_{q^n}\) as \(\mathbb{F}_q\)-vector space, a point \(P\in T_n\) is represented by its first \(n-1\) coordinates \((X_0,\dots,X_{n-2})\in\mathbb{F}_q^{n-1}\) in this basis, together with an equation in \(\mathbb{F}_q[x_0,\dots,x_{n-1}]\) which vanishes on the coordinates of any \(P\in T_n\), where \(x_0,\dots,x_{n-1}\) are indeterminates over \(\mathbb{F}_q\). This representation, although not injective, identifies a small number of points, and is of optimal size. In order to obtain the equation for the representation of the elements of \(T_n\), the authors rely on the Semaev summation polynomials [\textit{I. Semaev}, ``Summation polynomials and the discrete logarithm problem on elliptic curves, preprint, \url{http://eprint.iacr.org/2004/031.pdf} (2004)]. These polynomials provide conditions on the \(x\)-coordinates of a finite number of points on an elliptic curve summing to \(\mathcal{O}\). The authors consider such polynomials applied to the Frobenius conjugates of any point \(P\in T_n\). Further, taking into account that each Semaev summation polynomial is a symmetric element of \(\mathbb{F}_q[x_0,\dots,x_{n-1}]\), it is expressed in terms of the elementary symmetric polynomials \(\mathbb{F}_q[z_1,\dots,z_n]\). As a consequence, a \textit{compression} of the representation of the points of \(T_n\) is obtained by computing the elementary symmetric polynomials in the \(x\)--coordinates of the Frobenius conjugates of a given \(P\in T_n\). The \textit{decompression} is obtained by using the ``symmetrized version of the corresponding Semaev summation polynomial. Finally, explicit equations are given for extensions of degree 3 and 5, and the cost of compression and decompression is analyzed.
- -coordinates for binary elliptic curves
- A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
- A new index calculus algorithm with complexity L(1/4+o(1)) in small characteristic
- Advances in Cryptology - CRYPTO 2003
- Algorithmic Number Theory
- Algorithmic Number Theory
- Computing pairings using x-coordinates only
- Constructive and destructive facets of Weil descent on elliptic curves
- Discrete logarithm in \(\mathrm{GF}(2^{809})\) with FFS
- Efficient and Secure Algorithms for GLV-Based Scalar Multiplication and Their Implementation on GLV-GLS Curves
- Elliptic curve discrete logarithm problem over small degree extension fields
- Endomorphisms for faster elliptic curve cryptography on a large class of curves
- Four-dimensional Gallant-Lambert-Vanstone scalar multiplication
- High-speed high-security signatures
- scientific article; zbMATH DE number 1594291 (Why is no real title available?)
- scientific article; zbMATH DE number 176613 (Why is no real title available?)
- scientific article; zbMATH DE number 1024494 (Why is no real title available?)
- scientific article; zbMATH DE number 1942430 (Why is no real title available?)
- scientific article; zbMATH DE number 2042679 (Why is no real title available?)
- scientific article; zbMATH DE number 1748068 (Why is no real title available?)
- scientific article; zbMATH DE number 1759768 (Why is no real title available?)
- scientific article; zbMATH DE number 2155360 (Why is no real title available?)
- scientific article; zbMATH DE number 1842492 (Why is no real title available?)
- Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem
- Modern computer algebra
- On the Discrete Logarithm Problem on Algebraic Tori
- On the function field sieve and the impact of higher splitting probabilities. Application to discrete logarithms in \(\mathbb{F}_{2^{1971}}\) and \(\mathbb{F}_{2^{3164}}\)
- Point compression for Koblitz elliptic curves
- Public-key cryptosystems based on cubic finite field extensions
- Solving a 6120 -bit DLP on a Desktop Computer
- The Magma algebra system. I: The user language
- Trace Zero Varieties over Fields of Characteristic 2 for Cryptographic Applications
- Using abelian varieties to improve pairing-based cryptography
- New point compression method for elliptic \(\mathbb{F}_{q^2}\)-curves of \(j\)-invariant 0
- Faster point compression for elliptic curves of \(j\)-invariant 0
- An optimal representation for the trace zero subgroup
- Smooth symmetric systems over a finite field and applications
- Index calculus in the trace zero variety
This page was built for publication: Point compression for the trace zero subgroup over a small degree extension field
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2340180)
