96 results sorted by ID
Fast computation of 2-isogenies in dimension 4 and cryptographic applications
Pierrick Dartois
Implementation
Dimension 4 isogenies have first been introduced in cryptography for the cryptanalysis of Supersingular Isogeny Diffie-Hellman (SIDH) and have been used constructively in several schemes, including SQIsignHD, a derivative of SQIsign isogeny based signature scheme. Unlike in dimensions 2 and 3, we can no longer rely on the Jacobian model and its derivatives to compute isogenies. In dimension 4 (and higher), we can only use theta-models. Previous works by Romain Cosset, David Lubicz and Damien...
Complete group law for genus 2 Jacobians on Jacobian coordinates
Elif Ozbay Gurler, Huseyin Hisil
Public-key cryptography
This manuscript provides complete, inversion-free, and explicit group law formulas in Jacobian coordinates for the genus 2 hyperelliptic curves of the form $y^2 = x^5 + a_3 x^3 + a_2 x^2 + a_1 x + a_0$ over a field $K$ with $char(K) \ne 2$. The formulas do not require the use of polynomial arithmetic operations such as resultant, mod, or gcd computations but only operations in $K$.
Pairing Optimizations for Isogeny-based Cryptosystems
Shiping Cai, Kaizhan Lin, Chang-An Zhao
Implementation
In isogeny-based cryptography, bilinear pairings are regarded as a powerful tool in various applications, including key compression, public-key validation and torsion basis generation. However, in most isogeny-based protocols, the performance of pairing computations is unsatisfactory due to the high computational cost of the Miller function. Reducing the computational expense of the Miller function is crucial for enhancing the overall performance of pairing computations in isogeny-based...
An algorithm for efficient detection of $(N,N)$-splittings and its application to the isogeny problem in dimension 2
Maria Corte-Real Santos, Craig Costello, Sam Frengley
Attacks and cryptanalysis
We develop an efficient algorithm to detect whether a superspecial genus 2 Jacobian is optimally $(N, N)$-split for each integer $N \leq 11$. Incorporating this algorithm into the best-known attack against the superspecial isogeny problem in dimension 2 gives rise to significant cryptanalytic improvements. Our implementation shows that when the underlying prime $p$ is 100 bits, the attack is sped up by a factor $25{\tt x}$; when the underlying prime is 200 bits, the attack is sped up by a...
A Note on Reimplementing the Castryck-Decru Attack and Lessons Learned for SageMath
Rémy Oudompheng, Giacomo Pope
Attacks and cryptanalysis
This note describes the implementation of the Castryck-Decru key recovery attack on SIDH using the computer algebra system, SageMath. We describe in detail alternate computation methods for the isogeny steps of the original attack ($(2,2)$-isogenies from a product of elliptic curves and from a Jacobian), using explicit formulas to compute values of these isogenies at given points, motivated by both performance considerations and working around SageMath limitations. A performance analysis is...
Projective Geometry of Hessian Elliptic Curves and Genus 2 Triple Covers of Cubics
Rémy Oudompheng
Foundations
The existence of finite maps from hyperelliptic curves to elliptic curves has been studied for more than a century and their existence has been related to isogenies between a product of elliptic curves and their Jacobian surface.
Such finite covers, sometimes named gluing maps have recently appeared in cryptography in the context of genus 2 isogenies and more spectacularly, in the work of Castryck and Decru about the cryptanalysis of SIKE.
Computation methods include the use of algebraic...
Hard Homogeneous Spaces from the Class Field Theory of Imaginary Hyperelliptic Function Fields
Antoine Leudière, Pierre-Jean Spaenlehauer
Public-key cryptography
We explore algorithmic aspects of a free and transitive commutative group action
coming from the class field theory of imaginary hyperelliptic function fields.
Namely, the Jacobian of an imaginary hyperelliptic curve defined over
$\mathbb{F}_q$ acts on a subset of isomorphism classes of Drinfeld modules. We
describe an algorithm to compute the group action efficiently. This is a
function field analog of the Couveignes-Rostovtsev-Stolbunov group action. Our
proof-of-concept C++/NTL...
Multiradical isogenies
Wouter Castryck, Thomas Decru
Public-key cryptography
We argue that for all integers $N \geq 2$ and $g \geq 1$ there exist "multiradical" isogeny formulae, that can be iteratively applied to compute $(N^k, \ldots, N^k)$-isogenies between principally polarized $g$-dimensional abelian varieties, for any value of $k \geq 2$. The formulae are complete: each iteration involves the extraction of $g(g+1)/2$ different $N$th roots, whence the epithet multiradical, and by varying which roots are chosen one computes all $N^{g(g+1)/2}$ extensions to an...
Extending the GLS endomorphism to speed up GHS Weil descent using Magma
Jesús-Javier Chi-Domínguez, Francisco Rodríguez-Henríquez, Benjamin Smith
Public-key cryptography
Let \(q~=~2^n\), and let \(\mathcal{E} / \mathbb{F}_{q^{\ell}}\) be a generalized
Galbraith--Lin--Scott (GLS) binary curve, with $\ell \ge 2$ and \((\ell, n) = 1\).
We show that the GLS endomorphism on \(\mathcal{E} / \mathbb{F}_{q^{\ell}}\) induces an efficient
endomorphism on the Jacobian \(\mathrm{Jac}_\mathcal{H}(\mathbb{F}_q)\) of the genus-\(g\) hyperelliptic
curve \(\mathcal{H}\) corresponding to the image of the GHS Weil-descent attack applied to
\(\mathcal{E} /...
Recovering or Testing Extended-Affine Equivalence
Anne Canteaut, Alain Couvreur, Léo Perrin
Secret-key cryptography
Extended Affine (EA) equivalence is the equivalence relation between two vectorial Boolean functions $F$ and $G$ such that there exist two affine permutations $A$, $B$, and an affine function $C$ satisfying $G = A \circ F \circ B + C$. While a priori simple, it is very difficult in practice to test whether two functions are EA-equivalent. This problem has two variants: EA-testing deals with figuring out whether the two functions can be EA-equivalent, and EA-recovery is about recovering the...
A New Twofold Cornacchia-Type Algorithm and Its Applications
Bei Wang, Yi Ouyang, Honggang Hu, Songsong Li
Public-key cryptography
We focus on exploring more potential of Longa and Sica's algorithm (ASIACRYPT 2012), which is an elaborate iterated Cornacchia algorithm that can compute short bases for 4-GLV decompositions. The algorithm consists of two sub-algorithms, the first one in the ring of integers $\mathbb{Z}$ and the second one in the Gaussian integer ring $\mathbb{Z}[i]$. We observe that $\mathbb{Z}[i]$ in the second sub-algorithm can be replaced by another Euclidean domain $\mathbb{Z}[\ Omega ]$...
Automorphisms and isogeny graphs of abelian varieties, with applications to the superspecial Richelot isogeny graph
Enric Florit, Benjamin Smith
We investigate special structures due to automorphisms in isogeny graphs of principally polarized abelian varieties, and abelian surfaces in particular. We give theoretical and experimental results on the spectral and statistical properties of (2, 2)-isogeny graphs of superspecial abelian surfaces, including stationary distributions for random walks, bounds on eigenvalues and diameters, and a proof of the connectivity of the Jacobian subgraph of the (2, 2)-isogeny graph. Our results improve...
Getting Rid of Linear Algebra in Number Theory Problems
Paul Kirchner, Pierre-Alain Fouque
Public-key cryptography
We revisit some well-known cryptographic problems in a black box modular ring model of computation. This model allows us to compute with black box access to the ring $\mathbb{Z}/m\mathbb{Z}$. We develop new generic ring algorithms to recover $m$ even if it is unknown. At the end, Maurer's generic algorithm allows to recover an element from its black box representation. However, we avoid Maurer's idealized model with CDH oracle for the multiplication in the hidden ring by introducing a new...
Arguments of Knowledge via hidden order groups
Steve Thakur
Cryptographic protocols
We study non-interactive arguments of knowledge (AoKs) for commitments in groups of hidden order. We provide protocols whereby a Prover can demonstrate certain properties of and relations between committed sets/multisets, with succinct proofs that are publicly verifiable against the constant-sized commitments. In particular, we provide AoKs for the disjointness of committed sets/multisets in cryptographic accumulators, with a view toward applications to verifiably outsourcing data storage...
The security of Groups of Unknown Order based on Jacobians of Hyperelliptic Curves
Jonathan Lee
Cryptographic protocols
Recent work using groups of unknown order to construct verifiable delay functions, polynomial commitment schemes and non interactive zero knowledge proofs have provoked fresh interest in the construction of efficient cryptographic groups of unknown order. It has been suggested that the Jacobian of hyperelliptic curves of genus 3 could be suitable for this purpose. Regrettably, efficient algorithms to compute the order of the Jacobian of a hyperelliptic curve are known. Concretely, it is...
On the Complexity of ``Superdetermined'' Minrank Instances
Javier Verbel, John Baena, Daniel Cabarcas, Ray Perlner, Daniel Smith-Tone
Foundations
The Minrank (MR) problem is a computational problem closely related to attacks on code- and multivariate-based schemes.
In this paper we revisit the so-called Kipnis-Shamir (KS) approach to this problem. We extend previous complexity analysis by exposing non-trivial syzygies through the analysis of the Jacobian of the resulting system, with respect to a group of variables. We focus on a particular set of instances that yield a very overdetermined system which we refer to as...
Optimal TNFS-secure pairings on elliptic curves with composite embedding degree
Georgios Fotiadis, Chloe Martindale
Public-key cryptography
In this paper we present a comprehensive comparison between pairing-friendly elliptic curves, considering different curve forms and twists where possible. We define a measure of the efficiency of a parametrized pairing-friendly family that takes into account the number field sieve (NFS) attacks (unlike the $\rho$-value). This measure includes an approximation of the security of the discrete logarithm problem in $\mathbb F_{p^k}^*$, computed via the method of Barbulescu and Duquesne [4]. We...
Elliptic Curves in Generalized Huff's Model
Ronal Pranil Chand, Maheswara Rao Valluri
Abstract This paper introduces a new form of elliptic curves in generalized Huff's model. These curves endowed with the addition are shown to be a group over a finite field. We present formulae for point addition and doubling point on the curves, and evaluate the computational cost of point addition and doubling point using projective, Jacobian, Lopez-Dahab coordinate systems, and embedding of the curves into \mathbb{P}^{1}\times\mathbb{P}^{1} system. We also prove that the curves are...
Genus 2 curves with given split Jacobian
Jasper Scholten
Foundations
We construct a genus 2 curve inside the product of 2 elliptic curves. The formula for this construction has appeared in a previous paper. The current paper discusses how this formula arises naturally by using some theory of elliptic Kummer surfaces
Reduced Mumford divisors of a genus 2 curve through its jacobian function field
Eduardo Ruiz Duarte
We explore the function field of the jacobian JH of a hyperelliptic
curve H of genus 2 in order to find reduced coordinates to represent
points of JH and do arithmetic.
We show how this relates to the usual Mumford representation of points
of JH. Moreover we identify the open subsets of JH where our reduced coordinates are defined, characterizing the elements which can be reduced and we discuss the group operation with them.
Fast, uniform scalar multiplication for genus 2 Jacobians with fast Kummers
Ping Ngai Chung, Craig Costello, Benjamin Smith
Implementation
We give one- and two-dimensional scalar multiplication algorithms for
Jacobians of genus~2 curves that operate by
projecting to Kummer surfaces, where we can
exploit faster and more uniform pseudomultiplication, before
recovering the proper "signed" output back on the Jacobian.
This extends the work of Lopez and Dahab, Okeya and Sakurai,
and Brier and Joye to genus 2, and also to two-dimensional scalar
multiplication. The technique is especially interesting in genus 2, because Kummer...
\(\mu\)Kummer: efficient hyperelliptic signatures and key exchange on microcontrollers
Joost Renes, Peter Schwabe, Benjamin Smith, Lejla Batina
We describe the design and implementation of efficient signature and key-exchange schemes for the AVR~ATmega and ARM Cortex~M0 microcontrollers, targeting the 128-bit security level. Our algorithms are based on an efficient Montgomery ladder scalar multiplication on the Kummer surface of Gaudry and Schost's genus-2 hyperelliptic curve, combined with the Jacobian point recovery technique of Chung, Costello, and Smith. Our results are the first to show the feasibility of software-only...
Constructing genus 3 hyperelliptic Jacobians with CM
Jennifer Balakrishnan, Sorina Ionica, Kristin Lauter, Christelle Vincent
Given a sextic CM field K, we give an explicit method for finding all genus 3 hyperelliptic curves defined over the complex whose Jacobians are simple and have complex multiplication by the maximal order of this field, via an approximation of their Rosenhain invariants. Building on the work of Weng, we give an algorithm which works in complete generality, for any CM sextic field K, and computes minimal polynomials of the Rosenhain invariants for any period matrix of the Jacobian. This...
Computing Jacobi's \theta in quasi-linear time
Hugo Labrande
Public-key cryptography
Jacobi's \theta function has numerous applications in mathematics and computer science; a naive algorithm allows the computation of \theta(z, \tau), for z, \tau verifying certain conditions, with precision P in O(M(P) \sqrt{P}) bit operations, where M(P) denotes the number of operations needed to multiply two complex P-bit numbers. We generalize an algorithm which computes specific values of the \theta function (the theta-constants) in asymptotically faster time; this gives us an algorithm...
Fast, uniform, and compact scalar multiplication for elliptic curves and genus 2 Jacobians with applications to signature schemes
Ping Ngai Chung, Craig Costello, Benjamin Smith
Implementation
We give a general framework for uniform, constant-time one- and two-dimensional scalar multiplication algorithms for elliptic curves and Jacobians of genus~2 curves that operate by projecting to the \(x\)-line or Kummer surface, where we can exploit faster and more uniform pseudomultiplication, before recovering the proper ``signed'' output back on the curve or Jacobian.
This extends the work of López and Dahab, Okeya and Sakurai, and Brier and Joye to genus~2, and also to two-dimensional...
A classification of elliptic curves with respect to the GHS attack in odd characteristic
Tsutomu Iijima, Fumiyuki Momose, Jinhui Chao
Public-key cryptography
The GHS attack is known to solve discrete logarithm problems (DLP) in the Jacobian of a curve C_0 defined over the d degree extension field k_d of k:=GF(q) by mapping it to the DLP in the Jacobian of a covering curve C of C_0 over k. Recently, classifications for all elliptic curves and hyperelliptic curves C_0/k_d of genus 2,3 which possess (2,...,2)-covering C/k of P^1 were shown under an isogeny condition (i.e. when g(C) = d * g(C_0)). This paper presents a systematic classification...
Double-and-Add with Relative Jacobian Coordinates
Björn Fay
Implementation
One of the most efficient ways to implement a scalar multiplication on elliptic curves with precomputed points is to use mixed coordinates (affine and Jacobian). We show how to relax these preconditions by introducing relative Jacobian coordinates and give an algorithm to compute a scalar multiplication where the precomputed points can be given in Jacobian coordinates. We also show that this new approach is compatible with Meloni’s trick, which was already used in other papers to reduce the...
A New Method for Decomposition in the Jacobian of Small Genus Hyperelliptic Curves
Palash Sarkar, Shashank Singh
Foundations
Decomposing a divisor over a suitable factor basis in the Jacobian of a hyperelliptic curve is a crucial step in an
index calculus algorithm for the discrete log problem in the Jacobian. For small genus curves, in the year 2000, Gaudry had proposed
a suitable factor basis and a decomposition method. In this work, we provide a new method for decomposition over the same factor
basis. The advantage of the new method is that it admits a sieving technique which removes smoothness checking of...
Jacobian Coordinates on Genus 2 Curves
Huseyin Hisil, Craig Costello
Public-key cryptography
This paper presents a new projective coordinate system and new explicit algorithms which together boost the speed of arithmetic in the divisor class group of genus 2 curves. The proposed formulas generalise the use of Jacobian coordinates on elliptic curves, and their application improves the speed of performing cryptographic scalar multiplications in Jacobians of genus 2 curves over prime fields by an approximate factor of 1.25x. For example, on a single core of an Intel Core i7-3770M (Ivy...
Explicit endomorphism of the Jacobian of a hyperelliptic function field of genus 2 using base field operations
Eduardo Ruiz Duarte, Octavio Páez Osuna
Public-key cryptography
We present an efficient endomorphism for the Jacobian of a curve $C$ of genus 2 for divisors having a Non disjoint support. This extends the work of Costello in ~\cite{Costello} who calculated explicit formul\ae\space for divisor doubling and addition of divisors with disjoint support in $\jacobian(C)$ using only base field operations. Explicit formul\ae\space is presented for this third case and a different approach for divisor doubling.
Torsion Limits and Riemann-Roch Systems for Function Fields and Applications
Ignacio Cascudo, Ronald Cramer, Chaoping Xing
The Ihara limit (or constant) $A(q)$ has been a central problem of study in the asymptotic theory of global function fields (or equivalently, algebraic curves over finite fields). It addresses global function fields with many rational points and,
so far, most applications of this theory do not
require additional properties. Motivated by recent applications, we require global function fields
with the additional property that their zero class divisor groups contain at most a small number...
Equations System coming from Weil descent and subexponential attack for algebraic curve cryptosystem
Koh-ichi Nagao
Faugére et al. shows that the decomposition problem of a point of
elliptic curve over binary field $F_{2^n}$ reduces to solving low degree equations system
over $F_2$ coming from Weil descent. Using this method, the discrete logarithm problem of elliptic curve over
$F_{2^n}$ reduces to linear constrains, i.e., solving equations system using linear algebra
of monomial modulo field equations, and its complexity is expected to be subexponential of input size $n$. However, it is pity that at...
Decomposition formula of the Jacobian group of plane curve
Koh-ichi Nagao
Foundations
We give an algorithm for decomposing given element of Jacobian gruop
into the sum of the decomposed factor, which consists of certain subset of the points of curve.
On a Relation between the Ate Pairing and the Weil Pairing for Supersingular Elliptic Curves
Takakazu Satoh
Public-key cryptography
The hyperelliptic curve Ate pairing provides an efficient way to compute a
bilinear pairing on the Jacobian variety of a hyperelliptic curve.
We prove that, for supersingular elliptic curves with embedding degree
two, square of the Ate pairing is nothing but the Weil pairing.
Using the formula, we develop an X-coordinate only pairing inversion method.
However, the algorithm is still infeasible for cryptographic size problems.
Classification of Elliptic/hyperelliptic Curves with Weak Coverings against the GHS attack under an Isogeny Condition
Tsutomu Iijima, Fumiyuki Momose, Jinhui Chao
Public-key cryptography
The GHS attack is known to map the discrete logarithm problem(DLP) in the Jacobian of a curve $C_{0}$ defined over the $d$ degree extension $k_{d}$ of a finite field $k$ to the DLP in the Jacobian of a new curve $C$ over $k$ which is a covering curve of $C_0$, then solve the DLP of curves $C/k$ by variations of index calculus algorithms. It is therefore important to know which curve $C_0/k_d$ is subjected to the GHS attack, especially those whose covering $C/k$ have the smallest genus...
Four-dimensional GLV via the Weil restriction
Aurore Guillevic, Sorina Ionica
The Gallant-Lambert-Vanstone (GLV) algorithm uses efficiently computable endomorphisms to accelerate the computation of scalar multiplication of points on an abelian variety. Freeman and Satoh proposed for cryptographic use two families of genus 2 curves defined over $\F_{p}$ which have the property that the corresponding Jacobians are $(2,2)$-isogenous over an extension field to a product of elliptic curves defined over $\F_{p^2}$. We exploit the relationship between the endomorphism rings...
Fast Cryptography in Genus 2
Joppe W. Bos, Craig Costello, Huseyin Hisil, Kristin Lauter
In this paper we highlight the benefits of using genus 2 curves in public-key cryptography. Compared to the standardized genus 1 curves, or elliptic curves, arithmetic on genus 2 curves is typically more involved but allows us to work with moduli of half the size. We give a taxonomy of the best known techniques to realize genus 2 based cryptography, which includes fast formulas on the Kummer surface and efficient 4-dimensional GLV decompositions. By studying different modular arithmetic...
Constructing Pairing-Friendly Genus 2 Curves with Split Jacobian
Robert Drylo
Public-key cryptography
Genus 2 curves with simple but not absolutely simple jacobians can be used to construct pairing-based cryptosystems more efficient than for a generic genus 2 curve. We show that there is a full analogy between methods for constructing ordinary pairing-friendly elliptic curves and simple abelian varieties, which are iogenous over some extension to a product of elliptic curves. We extend the notion of complete, complete with variable discriminant, and sparse families introduced in by...
Pairing-based methods for genus 2 jacobians with maximal endomorphism ring
Sorina Ionica
Using Galois cohomology, Schmoyer characterizes cryptographic non-trivial self-pairings of the \ell-Tate pairing in terms of the action of the Frobenius on the \ell-torsion of the Jacobian of a genus 2 curve. We apply similar techniques to study the non-degeneracy of the \ell-Tate pairing restrained to subgroups of the \ell-torsion which are maximal isotropic with respect to the Weil pairing. First, we deduce a criterion to verify whether the jacobian of a genus 2 curve has maximal...
Genus 2 Hyperelliptic Curve Families with Explicit Jacobian Order Evaluation and Pairing-Friendly Constructions
Aurore Guillevic, Damien Vergnaud
Public-key cryptography
The use of (hyper)elliptic curves in cryptography relies on the ability to compute the Jacobian order of a given curve. Recently, Satoh proposed a probabilistic polynomial time algorithm to test whether the Jacobian -- over a finite field $\mathbb{F}_q$ -- of a hyperelliptic curve of the form $Y^2 = X^5 + aX^3 + bX$ (with $a,b \in \mathbb{F}_q^*$) has a large prime factor. His approach is to obtain candidates for the zeta function of the Jacobian over $\mathbb{F}_q^*$ from its zeta function...
On a new generalization of Huff curves
Abdoul Aziz Ciss, Djiby Sow
Public-key cryptography
Recently two kinds of Huff curves were introduced as elliptic curves models and their arithmetic was studied. It was also shown that they are suitable for cryptographic use such as Montgomery curves or Koblitz curves (in Weierstrass form) and Edwards curves.
In this work, we introduce the new generalized Huff curves $ax(y^{2} -c) = by(x^{2}-d)$ with $abcd(a^{2}c-b^{2}d)\neq 0$, which contains the generalized Huff's model $ax(y^{2}- d) = by(x^{2}-d)$ with $abd(a^{2}-b^{2})\neq 0$ of...
Fast and Regular Algorithms for Scalar Multiplication over Elliptic Curves
Matthieu Rivain
Implementation
Elliptic curve cryptosystems are more and more widespread in everyday-life applications. This trend should still gain momentum in coming years thanks to the exponential security enjoyed by these systems compared to the subexponential security of other systems such as RSA. For this reason, efficient elliptic curve arithmetic is still a hot topic for cryptographers. The core operation of elliptic curve cryptosystems is the scalar multiplication which multiplies some point on an elliptic curve...
Group Law Computations on Jacobians of Hyperelliptic Curves
Craig Costello, Kristin Lauter
We derive an explicit method of computing the composition step in Cantor's algorithm for group operations on Jacobians of hyperelliptic curves. Our technique is inspired by the geometric description of the group law and applies to hyperelliptic curves of arbitrary genus.
While Cantor's general composition involves arithmetic in the polynomial ring $F_q[x]$, the algorithm we propose solves a linear system over the base field which can be written down directly from the Mumford coordinates of...
Counting Points on Genus 2 Curves with Real Multiplication
P. Gaudry, D. Kohel, B. Smith
We present an accelerated Schoof-type point-counting algorithm for curves of genus 2 equipped with an efficiently computable real multiplication endomorphism. Our new algorithm reduces the complexity of genus 2 point counting over a finite field $GF(q)$ of large characteristic from $\sO(\log^8 q)$ to $\sO(\log^5 q)$. Using our algorithm we compute a 256-bit prime-order Jacobian, suitable for cryptographic applications, and also the order of a 1024-bit Jacobian.
Computing Discrete Logarithms in the Jacobian of High-Genus Hyperelliptic Curves over Even Characteristic Finite Fields
M. D. Velichka, M. J. Jacobson Jr., A. Stein
Foundations
We describe improved versions of index-calculus algorithms for solving discrete logarithm problems in Jacobians of high-genus hyperelliptic curves defined over even characteristic fields. Our first improvement is to incorporate several ideas for the low-genus case by Gaudry and Theriault, including the large prime variant and using a smaller factor base, into the large-genus algorithm of Enge and Gaudry. We extend the analysis in [24] to our new algorithm, allowing us to predict accurately...
Fast Endomorphism for any Genus 2 Hyperelliptic Curve over a Finite Field of Even Characteristic
Lei Li, Siman Yang
Public-key cryptography
In EUROCRYPT 2009, Galbraith, Lin and Scott constructed an efficiently computable endomorphism for a large family of elliptic curves defined over finite fields of large characteristic. They demonstrated that the endomorphism can be used to accelerate scalar multiplication in the elliptic curve cryptosystem based on these curves. In this paper we extend the method to any genus 2 hyperelliptic curve defined over a finite field of even characteristic. We propose an efficient algorithm to...
On the complexity of Decomposition Attack
Koh-ichi Nagao
Foundations
In recent researches, it is discovered that index calculus is
useful for solving the discrete logarithm problems (DLP) of the groups of the Jacobian of curves (including elliptic curve) over finite field, which are widely used to cryptosystems. In these cases, the probability that an element of the group is written by the summation of N elements of large primes and factor bases is O(1) where N is some pre-fixed constant. So the situation is little different to the normal index calculus and...
Co-Z Divisor Addition Formulae in Jacobian of Genus 2 Hyperelliptic Curves over Prime Fields
Vladislav Kovtun, Sergey Kavun
In this paper we proposed a new approach to divisor scalar multiplication in Jacobian of genus 2 hyperelliptic curves over fields with odd characteristic, without field inversion. It is based on improved addition formulae of the weight 2 divisors in projective divisor representation in most frequent case that suit very well to scalar multiplication algorithms based on Euclidean addition chains.
Deterministic Encoding and Hashing to Odd Hyperelliptic Curves
Pierre-Alain Fouque, Mehdi Tibouchi
Public-key cryptography
In this paper we propose a very simple and efficient encoding function from F_q to points of a hyperelliptic curve over F_q of the form H: y^2=f(x) where f is an odd polynomial. Hyperelliptic curves of this type have been frequently considered in the literature to obtain Jacobians of good order and pairing-friendly curves.
Our new encoding is nearly a bijection to the set of F_q-rational points on H. This makes it easy to construct well-behaved hash functions to the Jacobian J of H, as well...
Efficient Techniques for High-Speed Elliptic Curve Cryptography
Patrick Longa, Catherine Gebotys
Implementation
In this paper, a thorough bottom-up optimization process (field, point and scalar arithmetic) is used to speed up the computation of elliptic curve point multiplication and report new speed records on modern x86-64 based processors. Our different implementations include elliptic curves using Jacobian coordinates, extended Twisted Edwards coordinates and the recently proposed Galbraith-Lin-Scott (GLS) method. Compared to state-of-the-art implementations on identical platforms the proposed...
Co-Z Addition Formulae and Binary Ladders on Elliptic Curves
Raveen R. Goundar, Marc Joye, Atsuko Miyaji
Implementation
Meloni recently introduced a new type of arithmetic on elliptic curves when adding projective points sharing the same Z-coordinate. This paper presents further co-Z addition formulae (and register allocations) for various point additions on Weierstrass elliptic curves. It explains how the use of conjugate point addition and other implementation tricks allow one to develop efficient scalar multiplication algorithms making use of co-Z arithmetic. Specifically, this paper describes efficient...
Computing genus 2 curves from invariants on the Hilbert moduli space
Kristin Lauter, Tonghai Yang
Public-key cryptography
We give a new method for generating genus 2 curves over a finite field with a given number of points on the Jacobian of the curve. We define two new invariants for genus 2 curves as values of modular functions on the Hilbert moduli space and show how to compute them. We relate them to the usual three Igusa invariants on the Siegel moduli space and give an algorithm to construct curves using these new invariants. Our approach simplifies the complex analytic method for computing genus 2...
Genus 2 Curves with Complex Multiplication
Eyal Z. Goren, Kristin E. Lauter
Public-key cryptography
Genus 2 curves are useful in cryptography for both discrete-log based and pairing-based systems, but a method is required to compute genus 2 curves with Jacobian with a given number of points. Currently, all known methods involve constructing genus 2 curves with complex multiplication via computing their 3 Igusa class polynomials. These polynomials have rational coefficients and require extensive computation and precision to compute. Both the computation and the complexity analysis of...
Classification of Elliptic/hyperelliptic Curves with Weak Coverings against GHS Attack without Isogeny Condition
Tsutomu Iijima, Fumiyuki Momose, Jinhui Chao
Public-key cryptography
The GHS attack is known as a method to map the discrete logarithm problem(DLP) in the Jacobian of a curve C_{0} defined over the d degree extension k_{d} of a finite field k to the DLP in the Jacobian of a new curve C over k which is a covering curve of C_{0}.
Recently, classification and density analysis were shown for all elliptic and hyperelliptic curves C_{0}/k_d of genus 2, 3 which possess (2, \ldots,2) covering C/k of {\mathbb{P}^{1}} under the isogeny condition (i.e. when g(C)=d...
Faster Computation of the Tate Pairing
Christophe Arene, Tanja Lange, Michael Naehrig, Christophe Ritzenthaler
Public-key cryptography
This paper proposes new explicit formulas for the doubling and
addition steps in Miller's algorithm to compute the Tate pairing on elliptic
curves in Weierstrass and in Edwards form.
For Edwards curves the formulas come from a new way of seeing
the arithmetic.
We state the first geometric interpretation of the group law
on Edwards curves by presenting the functions which arise in
addition and doubling. The Tate pairing on Edwards curves can be computed by
using these functions in Miller's...
Constructing pairing-friendly hyperelliptic curves using Weil restriction
David Mandell Freeman, Takakazu Satoh
Public-key cryptography
A pairing-friendly curve is a curve over a finite field whose Jacobian has small embedding degree with respect to a large prime-order subgroup. In this paper we construct pairing-friendly genus 2 curves over finite fields $\mathbb{F}_q$ whose Jacobians are ordinary and simple, but not absolutely simple. We show that constructing such curves is equivalent to constructing elliptic curves over $\mathbb{F}_q$ that become pairing-friendly over a finite extension of $\mathbb{F}_q$. Our main...
A CM construction for curves of genus 2 with p-rank 1
Laura Hitt O'Connor, Gary McGuire, Michael Naehrig, Marco Streng
Foundations
We construct Weil numbers corresponding to genus-2 curves with $p$-rank 1 over the finite field $\F_{p^2}$ of $p^2$ elements. The corresponding curves can be constructed using explicit CM constructions. In one of our algorithms, the group of $\F_{p^2}$-valued points of the Jacobian has prime order, while another allows for a prescribed embedding degree with respect to a subgroup of prescribed order. The curves are defined over $\F_{p^2}$ out of necessity: we show that curves of $p$-rank 1...
Generating genus two hyperelliptic curves over large characteristic finite fields
Takakazu Satoh
Public-key cryptography
In hyperelliptic curve cryptography, finding a suitable
hyperelliptic curve is an important fundamental problem.
One of necessary conditions is that the order of its Jacobian
is a product of a large prime number and a small number.
In the paper, we give a probabilistic polynomial
time algorithm to test whether the Jacobian of the given hyperelliptic curve of the form $Y sup 2 = X sup 5 + u X sup 3 + v X$
satisfies the condition and, if so, gives the largest prime factor.
Our algorithm...
Another approach to pairing computation in Edwards coordinates
Sorina Ionica, Antoine Joux
The recent introduction of Edwards curves has significantly reduced
the cost of addition on elliptic curves. This paper presents new
explicit formulae for pairing implementation in Edwards coordinates.
We prove our method gives performances similar to those of Miller's
algorithm in Jacobian coordinates and is thus of cryptographic
interest when one chooses Edwards curve implementations of protocols
in elliptic curve cryptography. The method is faster than the recent
proposal of Das...
Efficient Hyperelliptic Arithmetic using Balanced Representation for Divisors
Steven D. Galbraith, Michael Harrison, David J. Mireles Morales
Foundations
We discuss arithmetic in the Jacobian of a
hyperelliptic curve $C$ of genus $g$. The traditional approach is to
fix a point $P_\infty \in C$ and represent divisor classes in the
form $E - d(P_\infty)$ where $E$ is effective and $0 \le d \le g$.
We propose a different representation which is balanced at infinity.
The resulting arithmetic is more efficient than previous approaches
when there are 2 points at infinity.
This is a corrected and extended version of the article presented in ANTS...
On Implementation of GHS Attack against Elliptic Curve Cryptosystems over Cubic Extension Fields of Odd Characteristics
Naoki Hashizume, Fumiyuki Momose, Jinhui Chao
In this paper, we present algorithms for implementation of the GHS attack to Elliptic curve cryptosystems (ECC). In particular, we consider two large classes of elliptic curves over cubic extension fields of odd characteristics which have weak covering curves against GHS attack, whose existence have been shown recently.
We show an algorithm to find definition equation of the covering curve and an algorithm to transfer DLP of the elliptic curve to Jacobian of the covering curve. An algorithm...
Fast Multiple Point Multiplication on Elliptic Curves over Prime and Binary Fields using the Double-Base Number System
Jithra Adikari, Vassil S. Dimitrov, Pradeep K. Mishra
Multiple-point multiplication on elliptic curves is
the highest computational complex operation in the elliptic curve
cyptographic based digital signature schemes. We describe three
algorithms for multiple-point multiplication on elliptic curves
over prime and binary fields, based on the representations
of two scalars, as sums of mixed powers of 2 and 3. Our
approaches include sliding window mechanism and some precomputed
values of points on the curve. A proof for formulae to
calculate the...
Setting Speed Records with the (Fractional) Multibase Non-Adjacent Form Method for Efficient Elliptic Curve Scalar Multiplication
Patrick Longa, Catherine Gebotys
Public-key cryptography
In this paper, we introduce the Fractional Window-w Multibase Non-Adjacent Form (Frac-wmbNAF) method to perform the scalar multiplication. This method generalizes the recently developed Window-w mbNAF (wmbNAF) method by allowing an unrestricted number of precomputed points. We then make a comprehensive analysis of the most recent and relevant methods existent in the literature for the ECC scalar multiplication, including the presented generalization and its original non-window version known...
Generators of Jacobians of Genus Two Curves
Christian Robenhagen Ravnshoj
We prove that in most cases relevant to cryptography, the Frobenius endomorphism on the Jacobian of a genus two curve is represented by a diagonal matrix with respect to an appropriate basis of the subgroup of l-torsion points. From this fact we get an explicit description of the Weil-pairing on the subgroup of l-torsion points. Finally, the
explicit description of the Weil-pairing provides us with an efficient, probabilistic algorithm to find generators of the subgroup of l-torsion points...
Fast explicit formulae for genus 2 hyperelliptic curves using projective coordinates (Updated)
Vladislav Kovtun, Thomas Wollinger
Implementation
This contribution proposes a modification of method of divisors group operation in the Jacobian of hyperelliptic curve over even and odd characteristic fields in projective coordinate. The hyperelliptic curve cryptosystem (HECC), enhances cryptographic security efficiency in e.g. information and telecommunications systems.
Pairing-friendly Hyperelliptic Curves with Ordinary Jacobians of Type $y^2=x^5+ax$
Mitsuru Kawazoe, Tetsuya Takahashi
Foundations
An explicit construction of pairing-friendly hyperelliptic curves with ordinary Jacobians
was firstly given by D.~Freeman. In this paper, we give other explicit constructions of pairing-friendly hyperelliptic curves with ordinary Jacobians based on the closed formulae
for the order of the Jacobian of a hyperelliptic curve of type $y^2=x^5+ax$. We present two methods in this paper. One is an analogue of the Cocks-Pinch method and the other is a cyclotomic method. By using these methods, we...
Non-Cyclic Subgroups of Jacobians of Genus Two Curves with Complex Multiplication
Christian Robenhagen Ravnshoj
Let E be an elliptic curve defined over a finite field. Balasubramanian and Koblitz have proved that if the l-th roots of unity m_l is not contained in the ground field, then a field extension of the ground
field contains m_l if and only if the l-torsion points of E are rational over the same field extension. We generalize this result to Jacobians of genus two curves with complex multiplication. In particular, we show that the Weil- and the Tate-pairing on such a Jacobian are non-degenerate...
Optimizing double-base elliptic-curve single-scalar multiplication
Daniel J. Bernstein, Peter Birkner, Tanja Lange, Christiane Peters
Public-key cryptography
This paper analyzes the best speeds that can be obtained for single-scalar multiplication with variable base point by combining a huge range of options:
– many choices of coordinate systems and formulas for individual group operations, including new formulas for tripling on Edwards curves;
– double-base chains with many different doubling/tripling ratios, including standard base-2 chains as an extreme case;
– many precomputation strategies, going beyond Dimitrov, Imbert, Mishra (Asiacrypt...
Pairings on Jacobians of Hyperelliptic Curves
Christian Robenhagen Ravnshoj
Public-key cryptography
Consider the jacobian of a hyperelliptic genus two curve defined over a finite field. Under certain restrictions on the endomorphism ring of the jacobian we give an explicit description all non-degenerate, bilinear, anti-symmetric and Galois-invariant pairings on the jacobian. From this description it follows that no such pairing can be computed more efficiently than the Weil pairing.
To establish this result, we need an explicit description of the representation of the Frobenius...
Faster addition and doubling on elliptic curves
Daniel J. Bernstein, Tanja Lange
Public-key cryptography
Edwards recently introduced a new normal form for elliptic curves.
Every elliptic curve over a non-binary field
is birationally equivalent to a curve in Edwards form
over an extension of the field,
and in many cases over the original field.
This paper presents fast
explicit formulas (and register allocations)
for group operations on an Edwards curve.
The algorithm for doubling
uses only 3M+4S, i.e., 3 field multiplications and 4 field squarings.
If curve parameters are chosen to be...
Embedding Degree of Hyperelliptic Curves with Complex Multiplication
Christian Robenhagen Ravnshoj
Consider the Jacobian of a genus two curve defined over a finite field and with complex multiplication. In this paper we show that if the l-Sylow subgroup of the Jacobian is not cyclic, then the embedding degree of the Jacobian with respect to l is one.
Generators of Jacobians of Hyperelliptic Curves
Christian Robenhagen Ravnshoj
Public-key cryptography
This paper provides a probabilistic algorithm to determine generators of the m-torsion subgroup of the Jacobian of a hyperelliptic curve of genus two.
Decomposed Attack for the Jacobian of a Hyperelliptic Curve over an Extension Field
Koh-ichi Nagao
We study the solution of the discrete logarithm problem for
the Jacobian of a curve of genus g defined over an extension field Fqn, by
decomposed attack, considering a external elements B0 given by points
of the curve whose x-coordinates are defined in Fq. In the decomposed
attack, an element of the group which is written by a sum of some elements
of external elements is called (potentially) decomposed and the
set of the terms, that appear in the sum, is called decomposed factor. In
order...
Large Cyclic Subgroups of Jacobians of Hyperelliptic Curves
Christian Robenhagen Ravnshøj
In this paper we obtain conditions on the divisors of the group order of the Jacobian of a hyperelliptic genus 2 curve, generated by the complex multiplication method described by Weng (2003) and Gaudry (2005). Examples, where these conditions imply that the Jacobian has a large cyclic subgroup, are given.
Computing endomorphism rings of Jacobians of genus 2 curves over finite fields
David Freeman, Kristin Lauter
Implementation
We present probabilistic algorithms which, given a genus 2 curve C defined over a finite field and a quartic CM field K, determine whether the endomorphism ring of the Jacobian J of C is the full ring of integers in K. In particular, we present algorithms for computing the field of definition of, and the action of Frobenius on, the subgroups J[l^d] for prime powers l^d. We use these algorithms to create the first implementation of Eisentrager and Lauter's algorithm for computing Igusa...
Families of genus 2 curves with small embedding degree
Laura Hitt
Hyperelliptic curves of small genus have the advantage of
providing a group of comparable size as that of elliptic curves,
while working over a field of smaller size. Pairing-friendly
hyperelliptic curves are those whose order of the Jacobian is
divisible by a large prime, whose embedding degree is small enough
for computations to be feasible, and whose minimal embedding field
is large enough for the discrete logarithm problem in it to be
difficult. We give a sequence of $\F_q$-isogeny...
On the Minimal Embedding Field
Laura Hitt
We discuss the underlying mathematics that causes the embedding
degree of a curve of any genus to not necessarily correspond to the
minimal embedding field, and hence why it may fail to capture the
security of a pairing-based cryptosystem. Let $C$ be a curve of
genus $g$ defined over a finite field $\F_q$, where $q=p^m$ for a
prime $p$. The Jacobian of the curve is an abelian variety,
$J_C(\F_q)$, of dimension $g$ defined over $\F_q$. For some prime
$N$, coprime to $p$, the embedding degree...
On the Security of Generalized Jacobian Cryptosystems
Isabelle Dechene
Generalized Jacobians are natural candidates to use in discrete logarithm (DL) based cryptography since they include the multiplicative group of finite fields, algebraic tori, elliptic curves as well as all Jacobians of curves. This thus led to the study of the simplest nontrivial generalized Jacobians of an elliptic curve, for which an efficient group law algorithm was recently obtained. With these explicit equations at hand, it is now possible to concretely study the corresponding discrete...
Extended Double-Base Number System with applications to Elliptic Curve Cryptography
Christophe Doche, Laurent Imbert
Public-key cryptography
We investigate the impact of larger digit sets on the length of
Double-Base Number system (DBNS) expansions.
We present a new representation system called {\em extended DBNS}
whose expansions can be extremely sparse.
When compared with double-base chains, the average length of
extended DBNS expansions of integers of size in the range 200--500 bits
is approximately reduced by $20\%$ using one precomputed point, $30\%$ using two, and $38\%$ using
four.
We also discuss a new approach to...
Efficient Scalar Multiplication and Security against Power Analysis in Cryptosystems based on the NIST Elliptic Curves Over Prime Fields
Lars Elmegaard-Fessel
Public-key cryptography
In cryptosystems based on elliptic curves over finite fields (ECC-systems), the most time-consuming operation is scalar multiplication. We focus on the NIST elliptic curves over prime fields. An implementation of scalar multiplication, developed by IBM Danmark A/S for test purposes, serves as a point of reference.
In order to achieve maximal efficiency in an ECC-system, one must choose an optimal method for scalar multiplication and the best possible coordinate representation for the curve...
Tate pairing for $y^{2}=x^{5}-\ Alpha x$ in Characteristic Five
Ryuichi Harasawa, Yutaka Sueyoshi, Aichi Kudo
In this paper, for the genus-$2$ hyperelliptic curve
$y^{2}=x^{5} -\ Alpha x$ ($\ Alpha = \pm2$) defined over finite fields of characteristic five,
we construct a distortion map explicitly, and show the map indeed
gives an input for which the value of the Tate pairing is not trivial.
Next we describe a computation of the Tate pairing
by using the proposed distortion map.
Furthermore, we also see that this type of curve
is equipped with a simple quintuple operation on the Jacobian group,
which...
Efficient Doubling on Genus 3 Curves over Binary Fields
Xinxin Fan, Thomas Wollinger, Yumin Wang
Implementation
The most important and expensive operation in a hyperelliptic curve
cryptosystem (HECC) is scalar multiplication by an integer k, i.e., computing an integer k times a divisor D on the Jacobian. Using some recoding algorithms for scalar $k$, we can reduce a number of divisor class additions during the process of computing scalar multiplication. So divisor doubling will account for the main part in all kinds of scalar multiplication algorithms. In order to accelerate the genus 3 HECC over...
Generation of random Picard curves for cryptography
Annegret Weng
Public-key cryptography
Based on ideas in an earlier paper by Mark Bauer, Edlyn Teske and myself and ideas of Pierrick Gaudry and Eric Schost, we present an algorithm for counting the number of elements in the Jacobian of a random Picard curve over a finite prime field of cryptosize. We give two examples of curves with a Jacobian of prime group order.
A Comparison of Point Counting methods for Hyperelliptic Curves over Prime Fields and Fields of Characteristic 2
Colm O hEigeartaigh
Computing the order of the Jacobian of a hyperelliptic curve remains a
hard problem. It is usually essential to calculate the order of the
Jacobian to prevent certain sub-exponential attacks on the cryptosystem.
This paper reports on the viability of implementations of various
point-counting techniques. We also report on the scalability of the
algorithms as the fields grow larger.
Scalar Multiplication in Elliptic Curve Cryptosystems: Pipelining with Pre-computations
Pradeep Kumar Mishra
Implementation
The pipelining scheme proposed in~\cite{PKM04} is an efficient and secure scheme for computing scalar multiplication in Elliptic Curve Cryptosystems (ECC). The scheme proposed in~\cite{PKM04} does not assume any pre-computation. In this work we extend the scheme to the situation where the system allows some pre-computation and is capable of storing some precomputed values. Like the scheme proposed in~\cite{PKM04} our scheme uses an extra multiplier. On the performance front, it outperforms...
Improvement of Thériault Algorithm of Index Calculus for Jacobian of Hyperelliptic Curves of Small Genus
Ko-ichi Nagao
Public-key cryptography
Gaudry present a variation of index calculus attack for solving the
DLP in the Jacobian of hyperelliptic curves. Harley and Thériault
improve these kind of algorithm. Here, we will present a variation of
these kind of algorithm, which is faster than previous ones.
Its complexity is $O(2-\frac{2}{g}+\epsilon)$.
Recently, P. Gaudry and E. Thomé
http://eprint.iacr.org/2004/153/
present the algorithm, whose complexity is same as our results.
So I submit my manuscript to this eprint archive.
Suitable Curves for Genus-4 HCC over Prime Fields: Point Counting Formulae for Hyperelliptic Curves of type $y^2=x^{2k+1}+ax$
Mitsuhiro Haneda, Mitsuru Kawazoe, Tetsuya Takahashi
Public-key cryptography
Computing the order of the Jacobian group of a hyperelliptic curve
over a finite field is very important to construct
a hyperelliptic curve cryptosystem (HCC), because
to construct secure HCC, we need Jacobian groups of order in the form
$l(J\(Bcdot c$ where $l$ is a prime greater than about $2^{160}$ and
$c$ is a very small integer.
But even in the case of genus two,
known algorithms to compute the order of a Jacobian group for a general curve
need a very long running time over a large...
Fast addition on non-hyperelliptic genus $3$ curves
Stéphane Flon, Roger Oyono, Christophe Ritzenthaler
Public-key cryptography
We present a fast addition algorithm in the Jacobian of a genus $3$ non-hyperelliptic curve over a field of any characteristic. When the curve has a rational flex and $\textrm{char}(k) > 5$, the computational cost for addition is $148M+15SQ+2I$ and $165M+20SQ+2I$ for doubling. An appendix focuses on the computation of flexes in all characteristics. For large odd $q$, we also show that the set of rational points of a non-hyperelliptic curve of genus $3$ can not be an arc.
Classification of genus 2 curves over $\mathbb{F}_{2^n}$ and optimization of their arithmetic
Bertrand BYRAMJEE, Sylvain DUQUESNE
Public-key cryptography
To obtain efficient cryptosystems based on hyperelliptic curves, we studied genus 2 isomorphism classes of hyperelliptic curves in characteristic 2. We found general and optimal form for these curves, just as the short Weierstrass form for elliptic curves. We studied the security and the arithmetic on their jacobian. We also rewrote and optimized the formulas of Lange in characteristic 2, and we introduced a new system of coordinate. Therefore, we deduced the best form of hyperelliptic...
Index calculus for abelian varieties and the elliptic curve discrete logarithm problem
Pierrick Gaudry
Public-key cryptography
We propose an index calculus algorithm for the discrete logarithm problem on general abelian varieties. The main difference with the previous approaches is that we do not make use of any embedding into the Jacobian of a well-suited curve. We apply this algorithm to the Weil restriction of elliptic curves and hyperelliptic curves over small degree extension fields. In particular, our attack can solve all elliptic curve discrete logarithm problems defined over $GF(q^3)$ in time $O(q^{10/7})$,...
Parallelizing Explicit Formula for Arithmetic in the Jacobian of Hyperelliptic Curves
Pradeep Kumar Mishra, Palash Sarkar
Implementation
One of the recent thrust areas in research on hyperelliptic curve cryptography has been to obtain explicit formulae for performing arithmetic in the Jacobian of such curves. We continue this line of research by obtaining parallel versions of such formulae. Our first contribution is to develop a general methodology for obtaining parallel algorithm of any explicit formula. Any parallel algorithm obtained using our methodology is provably optimal in the number of multiplication rounds. We next...
Trace Zero Subvariety for Cryptosystems
Tanja Lange
We present a kind of group suitable for cryptographic
applications: the trace zero subvariety. The construction is
based on Weil descent from curves of genus two over
extension fields $\F_{p^n}$, $n=3$.
On the Jacobian of the curve the group can be seen as a prime order
subgroup, however, considering the construction as Weil descent we
can argue that the security is equivalent to that of groups based on
low-genus hyperelliptic curves over prime fields.
The advantage is that the complexity to...
Fast arithmetic on Jacobians of Picard curves
Stéphane Flon, Roger Oyono
Public-key cryptography
In this paper we present a fast addition algorithm in the Jacobian of a Picard curve over a finite field $\mathbb F _q$ of characteristic different from $3$. This algorithm has a nice geometric interpretation, comparable to the classic "chord and tangent" law for the elliptic curves. Computational cost for addition is $144M + 12SQ + 2I$ and $158M + 16SQ + 2I$ for doubling.
An Elliptic Curve Trapdoor System
Edlyn Teske
Public-key cryptography
We propose an elliptic curve trapdoor system which is of interest in
key escrow applications. In this system, a pair
($E_{\rm s}, E_{\rm pb}$) of elliptic curves over $\F_{2^{161}}$ is constructed with the following properties: (i) the Gaudry-Hess-Smart Weil descent attack reduces the elliptic curve discrete logarithm problem (ECDLP) in $E_{\rm s}(\F_{2^{161}})$ to a hyperelliptic curve DLP in the Jacobian of a curve of genus 7 or 8, which is computationally feasible, but by far not...
Counting Points for Hyperelliptic Curves of type $y^2=x^5+ax$ over Finite Prime Fields
Eisaku Furukawa, Mitsuru Kawazoe, Tetsuya Takahashi
Foundations
Counting rational points on Jacobian varieties of hyperelliptic curves
over finite fields is very important for constructing
hyperelliptic curve cryptosystems (HCC),
but known algorithms for general curves over given large prime
fields need very long running times.
In this article, we propose an extremely fast point counting algorithm for
hyperelliptic curves of type $y^2=x^5+ax$ over given large
prime fields $\Fp$, e.g. 80-bit fields.
For these curves, we also determine the necessary...
Efficient Arithmetic on Hyperelliptic Curves
Tanja Lange
Public-key cryptography
Using the Frobenius endomorphism the operation of computing
scalar-mulitples in the Jacobian of a hyperelliptic curve is sped-up
considerably. The kind of curves considered are Kobiltz i.e. subfield
curves, defined over a small finite field which are then considered
over a large extension field. We deal with computation of
the group order over various extension fields, algorithms to obtain
the mentioned speed-up, and experimental results concerning both
issues. Additionally an alternative...
Dimension 4 isogenies have first been introduced in cryptography for the cryptanalysis of Supersingular Isogeny Diffie-Hellman (SIDH) and have been used constructively in several schemes, including SQIsignHD, a derivative of SQIsign isogeny based signature scheme. Unlike in dimensions 2 and 3, we can no longer rely on the Jacobian model and its derivatives to compute isogenies. In dimension 4 (and higher), we can only use theta-models. Previous works by Romain Cosset, David Lubicz and Damien...
This manuscript provides complete, inversion-free, and explicit group law formulas in Jacobian coordinates for the genus 2 hyperelliptic curves of the form $y^2 = x^5 + a_3 x^3 + a_2 x^2 + a_1 x + a_0$ over a field $K$ with $char(K) \ne 2$. The formulas do not require the use of polynomial arithmetic operations such as resultant, mod, or gcd computations but only operations in $K$.
In isogeny-based cryptography, bilinear pairings are regarded as a powerful tool in various applications, including key compression, public-key validation and torsion basis generation. However, in most isogeny-based protocols, the performance of pairing computations is unsatisfactory due to the high computational cost of the Miller function. Reducing the computational expense of the Miller function is crucial for enhancing the overall performance of pairing computations in isogeny-based...
We develop an efficient algorithm to detect whether a superspecial genus 2 Jacobian is optimally $(N, N)$-split for each integer $N \leq 11$. Incorporating this algorithm into the best-known attack against the superspecial isogeny problem in dimension 2 gives rise to significant cryptanalytic improvements. Our implementation shows that when the underlying prime $p$ is 100 bits, the attack is sped up by a factor $25{\tt x}$; when the underlying prime is 200 bits, the attack is sped up by a...
This note describes the implementation of the Castryck-Decru key recovery attack on SIDH using the computer algebra system, SageMath. We describe in detail alternate computation methods for the isogeny steps of the original attack ($(2,2)$-isogenies from a product of elliptic curves and from a Jacobian), using explicit formulas to compute values of these isogenies at given points, motivated by both performance considerations and working around SageMath limitations. A performance analysis is...
The existence of finite maps from hyperelliptic curves to elliptic curves has been studied for more than a century and their existence has been related to isogenies between a product of elliptic curves and their Jacobian surface. Such finite covers, sometimes named gluing maps have recently appeared in cryptography in the context of genus 2 isogenies and more spectacularly, in the work of Castryck and Decru about the cryptanalysis of SIKE. Computation methods include the use of algebraic...
We explore algorithmic aspects of a free and transitive commutative group action coming from the class field theory of imaginary hyperelliptic function fields. Namely, the Jacobian of an imaginary hyperelliptic curve defined over $\mathbb{F}_q$ acts on a subset of isomorphism classes of Drinfeld modules. We describe an algorithm to compute the group action efficiently. This is a function field analog of the Couveignes-Rostovtsev-Stolbunov group action. Our proof-of-concept C++/NTL...
We argue that for all integers $N \geq 2$ and $g \geq 1$ there exist "multiradical" isogeny formulae, that can be iteratively applied to compute $(N^k, \ldots, N^k)$-isogenies between principally polarized $g$-dimensional abelian varieties, for any value of $k \geq 2$. The formulae are complete: each iteration involves the extraction of $g(g+1)/2$ different $N$th roots, whence the epithet multiradical, and by varying which roots are chosen one computes all $N^{g(g+1)/2}$ extensions to an...
Let \(q~=~2^n\), and let \(\mathcal{E} / \mathbb{F}_{q^{\ell}}\) be a generalized Galbraith--Lin--Scott (GLS) binary curve, with $\ell \ge 2$ and \((\ell, n) = 1\). We show that the GLS endomorphism on \(\mathcal{E} / \mathbb{F}_{q^{\ell}}\) induces an efficient endomorphism on the Jacobian \(\mathrm{Jac}_\mathcal{H}(\mathbb{F}_q)\) of the genus-\(g\) hyperelliptic curve \(\mathcal{H}\) corresponding to the image of the GHS Weil-descent attack applied to \(\mathcal{E} /...
Extended Affine (EA) equivalence is the equivalence relation between two vectorial Boolean functions $F$ and $G$ such that there exist two affine permutations $A$, $B$, and an affine function $C$ satisfying $G = A \circ F \circ B + C$. While a priori simple, it is very difficult in practice to test whether two functions are EA-equivalent. This problem has two variants: EA-testing deals with figuring out whether the two functions can be EA-equivalent, and EA-recovery is about recovering the...
We focus on exploring more potential of Longa and Sica's algorithm (ASIACRYPT 2012), which is an elaborate iterated Cornacchia algorithm that can compute short bases for 4-GLV decompositions. The algorithm consists of two sub-algorithms, the first one in the ring of integers $\mathbb{Z}$ and the second one in the Gaussian integer ring $\mathbb{Z}[i]$. We observe that $\mathbb{Z}[i]$ in the second sub-algorithm can be replaced by another Euclidean domain $\mathbb{Z}[\ Omega ]$...
We investigate special structures due to automorphisms in isogeny graphs of principally polarized abelian varieties, and abelian surfaces in particular. We give theoretical and experimental results on the spectral and statistical properties of (2, 2)-isogeny graphs of superspecial abelian surfaces, including stationary distributions for random walks, bounds on eigenvalues and diameters, and a proof of the connectivity of the Jacobian subgraph of the (2, 2)-isogeny graph. Our results improve...
We revisit some well-known cryptographic problems in a black box modular ring model of computation. This model allows us to compute with black box access to the ring $\mathbb{Z}/m\mathbb{Z}$. We develop new generic ring algorithms to recover $m$ even if it is unknown. At the end, Maurer's generic algorithm allows to recover an element from its black box representation. However, we avoid Maurer's idealized model with CDH oracle for the multiplication in the hidden ring by introducing a new...
We study non-interactive arguments of knowledge (AoKs) for commitments in groups of hidden order. We provide protocols whereby a Prover can demonstrate certain properties of and relations between committed sets/multisets, with succinct proofs that are publicly verifiable against the constant-sized commitments. In particular, we provide AoKs for the disjointness of committed sets/multisets in cryptographic accumulators, with a view toward applications to verifiably outsourcing data storage...
Recent work using groups of unknown order to construct verifiable delay functions, polynomial commitment schemes and non interactive zero knowledge proofs have provoked fresh interest in the construction of efficient cryptographic groups of unknown order. It has been suggested that the Jacobian of hyperelliptic curves of genus 3 could be suitable for this purpose. Regrettably, efficient algorithms to compute the order of the Jacobian of a hyperelliptic curve are known. Concretely, it is...
The Minrank (MR) problem is a computational problem closely related to attacks on code- and multivariate-based schemes. In this paper we revisit the so-called Kipnis-Shamir (KS) approach to this problem. We extend previous complexity analysis by exposing non-trivial syzygies through the analysis of the Jacobian of the resulting system, with respect to a group of variables. We focus on a particular set of instances that yield a very overdetermined system which we refer to as...
In this paper we present a comprehensive comparison between pairing-friendly elliptic curves, considering different curve forms and twists where possible. We define a measure of the efficiency of a parametrized pairing-friendly family that takes into account the number field sieve (NFS) attacks (unlike the $\rho$-value). This measure includes an approximation of the security of the discrete logarithm problem in $\mathbb F_{p^k}^*$, computed via the method of Barbulescu and Duquesne [4]. We...
Abstract This paper introduces a new form of elliptic curves in generalized Huff's model. These curves endowed with the addition are shown to be a group over a finite field. We present formulae for point addition and doubling point on the curves, and evaluate the computational cost of point addition and doubling point using projective, Jacobian, Lopez-Dahab coordinate systems, and embedding of the curves into \mathbb{P}^{1}\times\mathbb{P}^{1} system. We also prove that the curves are...
We construct a genus 2 curve inside the product of 2 elliptic curves. The formula for this construction has appeared in a previous paper. The current paper discusses how this formula arises naturally by using some theory of elliptic Kummer surfaces
We explore the function field of the jacobian JH of a hyperelliptic curve H of genus 2 in order to find reduced coordinates to represent points of JH and do arithmetic. We show how this relates to the usual Mumford representation of points of JH. Moreover we identify the open subsets of JH where our reduced coordinates are defined, characterizing the elements which can be reduced and we discuss the group operation with them.
We give one- and two-dimensional scalar multiplication algorithms for Jacobians of genus~2 curves that operate by projecting to Kummer surfaces, where we can exploit faster and more uniform pseudomultiplication, before recovering the proper "signed" output back on the Jacobian. This extends the work of Lopez and Dahab, Okeya and Sakurai, and Brier and Joye to genus 2, and also to two-dimensional scalar multiplication. The technique is especially interesting in genus 2, because Kummer...
We describe the design and implementation of efficient signature and key-exchange schemes for the AVR~ATmega and ARM Cortex~M0 microcontrollers, targeting the 128-bit security level. Our algorithms are based on an efficient Montgomery ladder scalar multiplication on the Kummer surface of Gaudry and Schost's genus-2 hyperelliptic curve, combined with the Jacobian point recovery technique of Chung, Costello, and Smith. Our results are the first to show the feasibility of software-only...
Given a sextic CM field K, we give an explicit method for finding all genus 3 hyperelliptic curves defined over the complex whose Jacobians are simple and have complex multiplication by the maximal order of this field, via an approximation of their Rosenhain invariants. Building on the work of Weng, we give an algorithm which works in complete generality, for any CM sextic field K, and computes minimal polynomials of the Rosenhain invariants for any period matrix of the Jacobian. This...
Jacobi's \theta function has numerous applications in mathematics and computer science; a naive algorithm allows the computation of \theta(z, \tau), for z, \tau verifying certain conditions, with precision P in O(M(P) \sqrt{P}) bit operations, where M(P) denotes the number of operations needed to multiply two complex P-bit numbers. We generalize an algorithm which computes specific values of the \theta function (the theta-constants) in asymptotically faster time; this gives us an algorithm...
We give a general framework for uniform, constant-time one- and two-dimensional scalar multiplication algorithms for elliptic curves and Jacobians of genus~2 curves that operate by projecting to the \(x\)-line or Kummer surface, where we can exploit faster and more uniform pseudomultiplication, before recovering the proper ``signed'' output back on the curve or Jacobian. This extends the work of López and Dahab, Okeya and Sakurai, and Brier and Joye to genus~2, and also to two-dimensional...
The GHS attack is known to solve discrete logarithm problems (DLP) in the Jacobian of a curve C_0 defined over the d degree extension field k_d of k:=GF(q) by mapping it to the DLP in the Jacobian of a covering curve C of C_0 over k. Recently, classifications for all elliptic curves and hyperelliptic curves C_0/k_d of genus 2,3 which possess (2,...,2)-covering C/k of P^1 were shown under an isogeny condition (i.e. when g(C) = d * g(C_0)). This paper presents a systematic classification...
One of the most efficient ways to implement a scalar multiplication on elliptic curves with precomputed points is to use mixed coordinates (affine and Jacobian). We show how to relax these preconditions by introducing relative Jacobian coordinates and give an algorithm to compute a scalar multiplication where the precomputed points can be given in Jacobian coordinates. We also show that this new approach is compatible with Meloni’s trick, which was already used in other papers to reduce the...
Decomposing a divisor over a suitable factor basis in the Jacobian of a hyperelliptic curve is a crucial step in an index calculus algorithm for the discrete log problem in the Jacobian. For small genus curves, in the year 2000, Gaudry had proposed a suitable factor basis and a decomposition method. In this work, we provide a new method for decomposition over the same factor basis. The advantage of the new method is that it admits a sieving technique which removes smoothness checking of...
This paper presents a new projective coordinate system and new explicit algorithms which together boost the speed of arithmetic in the divisor class group of genus 2 curves. The proposed formulas generalise the use of Jacobian coordinates on elliptic curves, and their application improves the speed of performing cryptographic scalar multiplications in Jacobians of genus 2 curves over prime fields by an approximate factor of 1.25x. For example, on a single core of an Intel Core i7-3770M (Ivy...
We present an efficient endomorphism for the Jacobian of a curve $C$ of genus 2 for divisors having a Non disjoint support. This extends the work of Costello in ~\cite{Costello} who calculated explicit formul\ae\space for divisor doubling and addition of divisors with disjoint support in $\jacobian(C)$ using only base field operations. Explicit formul\ae\space is presented for this third case and a different approach for divisor doubling.
The Ihara limit (or constant) $A(q)$ has been a central problem of study in the asymptotic theory of global function fields (or equivalently, algebraic curves over finite fields). It addresses global function fields with many rational points and, so far, most applications of this theory do not require additional properties. Motivated by recent applications, we require global function fields with the additional property that their zero class divisor groups contain at most a small number...
Faugére et al. shows that the decomposition problem of a point of elliptic curve over binary field $F_{2^n}$ reduces to solving low degree equations system over $F_2$ coming from Weil descent. Using this method, the discrete logarithm problem of elliptic curve over $F_{2^n}$ reduces to linear constrains, i.e., solving equations system using linear algebra of monomial modulo field equations, and its complexity is expected to be subexponential of input size $n$. However, it is pity that at...
We give an algorithm for decomposing given element of Jacobian gruop into the sum of the decomposed factor, which consists of certain subset of the points of curve.
The hyperelliptic curve Ate pairing provides an efficient way to compute a bilinear pairing on the Jacobian variety of a hyperelliptic curve. We prove that, for supersingular elliptic curves with embedding degree two, square of the Ate pairing is nothing but the Weil pairing. Using the formula, we develop an X-coordinate only pairing inversion method. However, the algorithm is still infeasible for cryptographic size problems.
The GHS attack is known to map the discrete logarithm problem(DLP) in the Jacobian of a curve $C_{0}$ defined over the $d$ degree extension $k_{d}$ of a finite field $k$ to the DLP in the Jacobian of a new curve $C$ over $k$ which is a covering curve of $C_0$, then solve the DLP of curves $C/k$ by variations of index calculus algorithms. It is therefore important to know which curve $C_0/k_d$ is subjected to the GHS attack, especially those whose covering $C/k$ have the smallest genus...
The Gallant-Lambert-Vanstone (GLV) algorithm uses efficiently computable endomorphisms to accelerate the computation of scalar multiplication of points on an abelian variety. Freeman and Satoh proposed for cryptographic use two families of genus 2 curves defined over $\F_{p}$ which have the property that the corresponding Jacobians are $(2,2)$-isogenous over an extension field to a product of elliptic curves defined over $\F_{p^2}$. We exploit the relationship between the endomorphism rings...
In this paper we highlight the benefits of using genus 2 curves in public-key cryptography. Compared to the standardized genus 1 curves, or elliptic curves, arithmetic on genus 2 curves is typically more involved but allows us to work with moduli of half the size. We give a taxonomy of the best known techniques to realize genus 2 based cryptography, which includes fast formulas on the Kummer surface and efficient 4-dimensional GLV decompositions. By studying different modular arithmetic...
Genus 2 curves with simple but not absolutely simple jacobians can be used to construct pairing-based cryptosystems more efficient than for a generic genus 2 curve. We show that there is a full analogy between methods for constructing ordinary pairing-friendly elliptic curves and simple abelian varieties, which are iogenous over some extension to a product of elliptic curves. We extend the notion of complete, complete with variable discriminant, and sparse families introduced in by...
Using Galois cohomology, Schmoyer characterizes cryptographic non-trivial self-pairings of the \ell-Tate pairing in terms of the action of the Frobenius on the \ell-torsion of the Jacobian of a genus 2 curve. We apply similar techniques to study the non-degeneracy of the \ell-Tate pairing restrained to subgroups of the \ell-torsion which are maximal isotropic with respect to the Weil pairing. First, we deduce a criterion to verify whether the jacobian of a genus 2 curve has maximal...
The use of (hyper)elliptic curves in cryptography relies on the ability to compute the Jacobian order of a given curve. Recently, Satoh proposed a probabilistic polynomial time algorithm to test whether the Jacobian -- over a finite field $\mathbb{F}_q$ -- of a hyperelliptic curve of the form $Y^2 = X^5 + aX^3 + bX$ (with $a,b \in \mathbb{F}_q^*$) has a large prime factor. His approach is to obtain candidates for the zeta function of the Jacobian over $\mathbb{F}_q^*$ from its zeta function...
Recently two kinds of Huff curves were introduced as elliptic curves models and their arithmetic was studied. It was also shown that they are suitable for cryptographic use such as Montgomery curves or Koblitz curves (in Weierstrass form) and Edwards curves. In this work, we introduce the new generalized Huff curves $ax(y^{2} -c) = by(x^{2}-d)$ with $abcd(a^{2}c-b^{2}d)\neq 0$, which contains the generalized Huff's model $ax(y^{2}- d) = by(x^{2}-d)$ with $abd(a^{2}-b^{2})\neq 0$ of...
Elliptic curve cryptosystems are more and more widespread in everyday-life applications. This trend should still gain momentum in coming years thanks to the exponential security enjoyed by these systems compared to the subexponential security of other systems such as RSA. For this reason, efficient elliptic curve arithmetic is still a hot topic for cryptographers. The core operation of elliptic curve cryptosystems is the scalar multiplication which multiplies some point on an elliptic curve...
We derive an explicit method of computing the composition step in Cantor's algorithm for group operations on Jacobians of hyperelliptic curves. Our technique is inspired by the geometric description of the group law and applies to hyperelliptic curves of arbitrary genus. While Cantor's general composition involves arithmetic in the polynomial ring $F_q[x]$, the algorithm we propose solves a linear system over the base field which can be written down directly from the Mumford coordinates of...
We present an accelerated Schoof-type point-counting algorithm for curves of genus 2 equipped with an efficiently computable real multiplication endomorphism. Our new algorithm reduces the complexity of genus 2 point counting over a finite field $GF(q)$ of large characteristic from $\sO(\log^8 q)$ to $\sO(\log^5 q)$. Using our algorithm we compute a 256-bit prime-order Jacobian, suitable for cryptographic applications, and also the order of a 1024-bit Jacobian.
We describe improved versions of index-calculus algorithms for solving discrete logarithm problems in Jacobians of high-genus hyperelliptic curves defined over even characteristic fields. Our first improvement is to incorporate several ideas for the low-genus case by Gaudry and Theriault, including the large prime variant and using a smaller factor base, into the large-genus algorithm of Enge and Gaudry. We extend the analysis in [24] to our new algorithm, allowing us to predict accurately...
In EUROCRYPT 2009, Galbraith, Lin and Scott constructed an efficiently computable endomorphism for a large family of elliptic curves defined over finite fields of large characteristic. They demonstrated that the endomorphism can be used to accelerate scalar multiplication in the elliptic curve cryptosystem based on these curves. In this paper we extend the method to any genus 2 hyperelliptic curve defined over a finite field of even characteristic. We propose an efficient algorithm to...
In recent researches, it is discovered that index calculus is useful for solving the discrete logarithm problems (DLP) of the groups of the Jacobian of curves (including elliptic curve) over finite field, which are widely used to cryptosystems. In these cases, the probability that an element of the group is written by the summation of N elements of large primes and factor bases is O(1) where N is some pre-fixed constant. So the situation is little different to the normal index calculus and...
In this paper we proposed a new approach to divisor scalar multiplication in Jacobian of genus 2 hyperelliptic curves over fields with odd characteristic, without field inversion. It is based on improved addition formulae of the weight 2 divisors in projective divisor representation in most frequent case that suit very well to scalar multiplication algorithms based on Euclidean addition chains.
In this paper we propose a very simple and efficient encoding function from F_q to points of a hyperelliptic curve over F_q of the form H: y^2=f(x) where f is an odd polynomial. Hyperelliptic curves of this type have been frequently considered in the literature to obtain Jacobians of good order and pairing-friendly curves. Our new encoding is nearly a bijection to the set of F_q-rational points on H. This makes it easy to construct well-behaved hash functions to the Jacobian J of H, as well...
In this paper, a thorough bottom-up optimization process (field, point and scalar arithmetic) is used to speed up the computation of elliptic curve point multiplication and report new speed records on modern x86-64 based processors. Our different implementations include elliptic curves using Jacobian coordinates, extended Twisted Edwards coordinates and the recently proposed Galbraith-Lin-Scott (GLS) method. Compared to state-of-the-art implementations on identical platforms the proposed...
Meloni recently introduced a new type of arithmetic on elliptic curves when adding projective points sharing the same Z-coordinate. This paper presents further co-Z addition formulae (and register allocations) for various point additions on Weierstrass elliptic curves. It explains how the use of conjugate point addition and other implementation tricks allow one to develop efficient scalar multiplication algorithms making use of co-Z arithmetic. Specifically, this paper describes efficient...
We give a new method for generating genus 2 curves over a finite field with a given number of points on the Jacobian of the curve. We define two new invariants for genus 2 curves as values of modular functions on the Hilbert moduli space and show how to compute them. We relate them to the usual three Igusa invariants on the Siegel moduli space and give an algorithm to construct curves using these new invariants. Our approach simplifies the complex analytic method for computing genus 2...
Genus 2 curves are useful in cryptography for both discrete-log based and pairing-based systems, but a method is required to compute genus 2 curves with Jacobian with a given number of points. Currently, all known methods involve constructing genus 2 curves with complex multiplication via computing their 3 Igusa class polynomials. These polynomials have rational coefficients and require extensive computation and precision to compute. Both the computation and the complexity analysis of...
The GHS attack is known as a method to map the discrete logarithm problem(DLP) in the Jacobian of a curve C_{0} defined over the d degree extension k_{d} of a finite field k to the DLP in the Jacobian of a new curve C over k which is a covering curve of C_{0}. Recently, classification and density analysis were shown for all elliptic and hyperelliptic curves C_{0}/k_d of genus 2, 3 which possess (2, \ldots,2) covering C/k of {\mathbb{P}^{1}} under the isogeny condition (i.e. when g(C)=d...
This paper proposes new explicit formulas for the doubling and addition steps in Miller's algorithm to compute the Tate pairing on elliptic curves in Weierstrass and in Edwards form. For Edwards curves the formulas come from a new way of seeing the arithmetic. We state the first geometric interpretation of the group law on Edwards curves by presenting the functions which arise in addition and doubling. The Tate pairing on Edwards curves can be computed by using these functions in Miller's...
A pairing-friendly curve is a curve over a finite field whose Jacobian has small embedding degree with respect to a large prime-order subgroup. In this paper we construct pairing-friendly genus 2 curves over finite fields $\mathbb{F}_q$ whose Jacobians are ordinary and simple, but not absolutely simple. We show that constructing such curves is equivalent to constructing elliptic curves over $\mathbb{F}_q$ that become pairing-friendly over a finite extension of $\mathbb{F}_q$. Our main...
We construct Weil numbers corresponding to genus-2 curves with $p$-rank 1 over the finite field $\F_{p^2}$ of $p^2$ elements. The corresponding curves can be constructed using explicit CM constructions. In one of our algorithms, the group of $\F_{p^2}$-valued points of the Jacobian has prime order, while another allows for a prescribed embedding degree with respect to a subgroup of prescribed order. The curves are defined over $\F_{p^2}$ out of necessity: we show that curves of $p$-rank 1...
In hyperelliptic curve cryptography, finding a suitable hyperelliptic curve is an important fundamental problem. One of necessary conditions is that the order of its Jacobian is a product of a large prime number and a small number. In the paper, we give a probabilistic polynomial time algorithm to test whether the Jacobian of the given hyperelliptic curve of the form $Y sup 2 = X sup 5 + u X sup 3 + v X$ satisfies the condition and, if so, gives the largest prime factor. Our algorithm...
The recent introduction of Edwards curves has significantly reduced the cost of addition on elliptic curves. This paper presents new explicit formulae for pairing implementation in Edwards coordinates. We prove our method gives performances similar to those of Miller's algorithm in Jacobian coordinates and is thus of cryptographic interest when one chooses Edwards curve implementations of protocols in elliptic curve cryptography. The method is faster than the recent proposal of Das...
We discuss arithmetic in the Jacobian of a hyperelliptic curve $C$ of genus $g$. The traditional approach is to fix a point $P_\infty \in C$ and represent divisor classes in the form $E - d(P_\infty)$ where $E$ is effective and $0 \le d \le g$. We propose a different representation which is balanced at infinity. The resulting arithmetic is more efficient than previous approaches when there are 2 points at infinity. This is a corrected and extended version of the article presented in ANTS...
In this paper, we present algorithms for implementation of the GHS attack to Elliptic curve cryptosystems (ECC). In particular, we consider two large classes of elliptic curves over cubic extension fields of odd characteristics which have weak covering curves against GHS attack, whose existence have been shown recently. We show an algorithm to find definition equation of the covering curve and an algorithm to transfer DLP of the elliptic curve to Jacobian of the covering curve. An algorithm...
Multiple-point multiplication on elliptic curves is the highest computational complex operation in the elliptic curve cyptographic based digital signature schemes. We describe three algorithms for multiple-point multiplication on elliptic curves over prime and binary fields, based on the representations of two scalars, as sums of mixed powers of 2 and 3. Our approaches include sliding window mechanism and some precomputed values of points on the curve. A proof for formulae to calculate the...
In this paper, we introduce the Fractional Window-w Multibase Non-Adjacent Form (Frac-wmbNAF) method to perform the scalar multiplication. This method generalizes the recently developed Window-w mbNAF (wmbNAF) method by allowing an unrestricted number of precomputed points. We then make a comprehensive analysis of the most recent and relevant methods existent in the literature for the ECC scalar multiplication, including the presented generalization and its original non-window version known...
We prove that in most cases relevant to cryptography, the Frobenius endomorphism on the Jacobian of a genus two curve is represented by a diagonal matrix with respect to an appropriate basis of the subgroup of l-torsion points. From this fact we get an explicit description of the Weil-pairing on the subgroup of l-torsion points. Finally, the explicit description of the Weil-pairing provides us with an efficient, probabilistic algorithm to find generators of the subgroup of l-torsion points...
This contribution proposes a modification of method of divisors group operation in the Jacobian of hyperelliptic curve over even and odd characteristic fields in projective coordinate. The hyperelliptic curve cryptosystem (HECC), enhances cryptographic security efficiency in e.g. information and telecommunications systems.
An explicit construction of pairing-friendly hyperelliptic curves with ordinary Jacobians was firstly given by D.~Freeman. In this paper, we give other explicit constructions of pairing-friendly hyperelliptic curves with ordinary Jacobians based on the closed formulae for the order of the Jacobian of a hyperelliptic curve of type $y^2=x^5+ax$. We present two methods in this paper. One is an analogue of the Cocks-Pinch method and the other is a cyclotomic method. By using these methods, we...
Let E be an elliptic curve defined over a finite field. Balasubramanian and Koblitz have proved that if the l-th roots of unity m_l is not contained in the ground field, then a field extension of the ground field contains m_l if and only if the l-torsion points of E are rational over the same field extension. We generalize this result to Jacobians of genus two curves with complex multiplication. In particular, we show that the Weil- and the Tate-pairing on such a Jacobian are non-degenerate...
This paper analyzes the best speeds that can be obtained for single-scalar multiplication with variable base point by combining a huge range of options: – many choices of coordinate systems and formulas for individual group operations, including new formulas for tripling on Edwards curves; – double-base chains with many different doubling/tripling ratios, including standard base-2 chains as an extreme case; – many precomputation strategies, going beyond Dimitrov, Imbert, Mishra (Asiacrypt...
Consider the jacobian of a hyperelliptic genus two curve defined over a finite field. Under certain restrictions on the endomorphism ring of the jacobian we give an explicit description all non-degenerate, bilinear, anti-symmetric and Galois-invariant pairings on the jacobian. From this description it follows that no such pairing can be computed more efficiently than the Weil pairing. To establish this result, we need an explicit description of the representation of the Frobenius...
Edwards recently introduced a new normal form for elliptic curves. Every elliptic curve over a non-binary field is birationally equivalent to a curve in Edwards form over an extension of the field, and in many cases over the original field. This paper presents fast explicit formulas (and register allocations) for group operations on an Edwards curve. The algorithm for doubling uses only 3M+4S, i.e., 3 field multiplications and 4 field squarings. If curve parameters are chosen to be...
Consider the Jacobian of a genus two curve defined over a finite field and with complex multiplication. In this paper we show that if the l-Sylow subgroup of the Jacobian is not cyclic, then the embedding degree of the Jacobian with respect to l is one.
This paper provides a probabilistic algorithm to determine generators of the m-torsion subgroup of the Jacobian of a hyperelliptic curve of genus two.
We study the solution of the discrete logarithm problem for the Jacobian of a curve of genus g defined over an extension field Fqn, by decomposed attack, considering a external elements B0 given by points of the curve whose x-coordinates are defined in Fq. In the decomposed attack, an element of the group which is written by a sum of some elements of external elements is called (potentially) decomposed and the set of the terms, that appear in the sum, is called decomposed factor. In order...
In this paper we obtain conditions on the divisors of the group order of the Jacobian of a hyperelliptic genus 2 curve, generated by the complex multiplication method described by Weng (2003) and Gaudry (2005). Examples, where these conditions imply that the Jacobian has a large cyclic subgroup, are given.
We present probabilistic algorithms which, given a genus 2 curve C defined over a finite field and a quartic CM field K, determine whether the endomorphism ring of the Jacobian J of C is the full ring of integers in K. In particular, we present algorithms for computing the field of definition of, and the action of Frobenius on, the subgroups J[l^d] for prime powers l^d. We use these algorithms to create the first implementation of Eisentrager and Lauter's algorithm for computing Igusa...
Hyperelliptic curves of small genus have the advantage of providing a group of comparable size as that of elliptic curves, while working over a field of smaller size. Pairing-friendly hyperelliptic curves are those whose order of the Jacobian is divisible by a large prime, whose embedding degree is small enough for computations to be feasible, and whose minimal embedding field is large enough for the discrete logarithm problem in it to be difficult. We give a sequence of $\F_q$-isogeny...
We discuss the underlying mathematics that causes the embedding degree of a curve of any genus to not necessarily correspond to the minimal embedding field, and hence why it may fail to capture the security of a pairing-based cryptosystem. Let $C$ be a curve of genus $g$ defined over a finite field $\F_q$, where $q=p^m$ for a prime $p$. The Jacobian of the curve is an abelian variety, $J_C(\F_q)$, of dimension $g$ defined over $\F_q$. For some prime $N$, coprime to $p$, the embedding degree...
Generalized Jacobians are natural candidates to use in discrete logarithm (DL) based cryptography since they include the multiplicative group of finite fields, algebraic tori, elliptic curves as well as all Jacobians of curves. This thus led to the study of the simplest nontrivial generalized Jacobians of an elliptic curve, for which an efficient group law algorithm was recently obtained. With these explicit equations at hand, it is now possible to concretely study the corresponding discrete...
We investigate the impact of larger digit sets on the length of Double-Base Number system (DBNS) expansions. We present a new representation system called {\em extended DBNS} whose expansions can be extremely sparse. When compared with double-base chains, the average length of extended DBNS expansions of integers of size in the range 200--500 bits is approximately reduced by $20\%$ using one precomputed point, $30\%$ using two, and $38\%$ using four. We also discuss a new approach to...
In cryptosystems based on elliptic curves over finite fields (ECC-systems), the most time-consuming operation is scalar multiplication. We focus on the NIST elliptic curves over prime fields. An implementation of scalar multiplication, developed by IBM Danmark A/S for test purposes, serves as a point of reference. In order to achieve maximal efficiency in an ECC-system, one must choose an optimal method for scalar multiplication and the best possible coordinate representation for the curve...
In this paper, for the genus-$2$ hyperelliptic curve $y^{2}=x^{5} -\ Alpha x$ ($\ Alpha = \pm2$) defined over finite fields of characteristic five, we construct a distortion map explicitly, and show the map indeed gives an input for which the value of the Tate pairing is not trivial. Next we describe a computation of the Tate pairing by using the proposed distortion map. Furthermore, we also see that this type of curve is equipped with a simple quintuple operation on the Jacobian group, which...
The most important and expensive operation in a hyperelliptic curve cryptosystem (HECC) is scalar multiplication by an integer k, i.e., computing an integer k times a divisor D on the Jacobian. Using some recoding algorithms for scalar $k$, we can reduce a number of divisor class additions during the process of computing scalar multiplication. So divisor doubling will account for the main part in all kinds of scalar multiplication algorithms. In order to accelerate the genus 3 HECC over...
Based on ideas in an earlier paper by Mark Bauer, Edlyn Teske and myself and ideas of Pierrick Gaudry and Eric Schost, we present an algorithm for counting the number of elements in the Jacobian of a random Picard curve over a finite prime field of cryptosize. We give two examples of curves with a Jacobian of prime group order.
Computing the order of the Jacobian of a hyperelliptic curve remains a hard problem. It is usually essential to calculate the order of the Jacobian to prevent certain sub-exponential attacks on the cryptosystem. This paper reports on the viability of implementations of various point-counting techniques. We also report on the scalability of the algorithms as the fields grow larger.
The pipelining scheme proposed in~\cite{PKM04} is an efficient and secure scheme for computing scalar multiplication in Elliptic Curve Cryptosystems (ECC). The scheme proposed in~\cite{PKM04} does not assume any pre-computation. In this work we extend the scheme to the situation where the system allows some pre-computation and is capable of storing some precomputed values. Like the scheme proposed in~\cite{PKM04} our scheme uses an extra multiplier. On the performance front, it outperforms...
Gaudry present a variation of index calculus attack for solving the DLP in the Jacobian of hyperelliptic curves. Harley and Thériault improve these kind of algorithm. Here, we will present a variation of these kind of algorithm, which is faster than previous ones. Its complexity is $O(2-\frac{2}{g}+\epsilon)$. Recently, P. Gaudry and E. Thomé http://eprint.iacr.org/2004/153/ present the algorithm, whose complexity is same as our results. So I submit my manuscript to this eprint archive.
Computing the order of the Jacobian group of a hyperelliptic curve over a finite field is very important to construct a hyperelliptic curve cryptosystem (HCC), because to construct secure HCC, we need Jacobian groups of order in the form $l(J\(Bcdot c$ where $l$ is a prime greater than about $2^{160}$ and $c$ is a very small integer. But even in the case of genus two, known algorithms to compute the order of a Jacobian group for a general curve need a very long running time over a large...
We present a fast addition algorithm in the Jacobian of a genus $3$ non-hyperelliptic curve over a field of any characteristic. When the curve has a rational flex and $\textrm{char}(k) > 5$, the computational cost for addition is $148M+15SQ+2I$ and $165M+20SQ+2I$ for doubling. An appendix focuses on the computation of flexes in all characteristics. For large odd $q$, we also show that the set of rational points of a non-hyperelliptic curve of genus $3$ can not be an arc.
To obtain efficient cryptosystems based on hyperelliptic curves, we studied genus 2 isomorphism classes of hyperelliptic curves in characteristic 2. We found general and optimal form for these curves, just as the short Weierstrass form for elliptic curves. We studied the security and the arithmetic on their jacobian. We also rewrote and optimized the formulas of Lange in characteristic 2, and we introduced a new system of coordinate. Therefore, we deduced the best form of hyperelliptic...
We propose an index calculus algorithm for the discrete logarithm problem on general abelian varieties. The main difference with the previous approaches is that we do not make use of any embedding into the Jacobian of a well-suited curve. We apply this algorithm to the Weil restriction of elliptic curves and hyperelliptic curves over small degree extension fields. In particular, our attack can solve all elliptic curve discrete logarithm problems defined over $GF(q^3)$ in time $O(q^{10/7})$,...
One of the recent thrust areas in research on hyperelliptic curve cryptography has been to obtain explicit formulae for performing arithmetic in the Jacobian of such curves. We continue this line of research by obtaining parallel versions of such formulae. Our first contribution is to develop a general methodology for obtaining parallel algorithm of any explicit formula. Any parallel algorithm obtained using our methodology is provably optimal in the number of multiplication rounds. We next...
We present a kind of group suitable for cryptographic applications: the trace zero subvariety. The construction is based on Weil descent from curves of genus two over extension fields $\F_{p^n}$, $n=3$. On the Jacobian of the curve the group can be seen as a prime order subgroup, however, considering the construction as Weil descent we can argue that the security is equivalent to that of groups based on low-genus hyperelliptic curves over prime fields. The advantage is that the complexity to...
In this paper we present a fast addition algorithm in the Jacobian of a Picard curve over a finite field $\mathbb F _q$ of characteristic different from $3$. This algorithm has a nice geometric interpretation, comparable to the classic "chord and tangent" law for the elliptic curves. Computational cost for addition is $144M + 12SQ + 2I$ and $158M + 16SQ + 2I$ for doubling.
We propose an elliptic curve trapdoor system which is of interest in key escrow applications. In this system, a pair ($E_{\rm s}, E_{\rm pb}$) of elliptic curves over $\F_{2^{161}}$ is constructed with the following properties: (i) the Gaudry-Hess-Smart Weil descent attack reduces the elliptic curve discrete logarithm problem (ECDLP) in $E_{\rm s}(\F_{2^{161}})$ to a hyperelliptic curve DLP in the Jacobian of a curve of genus 7 or 8, which is computationally feasible, but by far not...
Counting rational points on Jacobian varieties of hyperelliptic curves over finite fields is very important for constructing hyperelliptic curve cryptosystems (HCC), but known algorithms for general curves over given large prime fields need very long running times. In this article, we propose an extremely fast point counting algorithm for hyperelliptic curves of type $y^2=x^5+ax$ over given large prime fields $\Fp$, e.g. 80-bit fields. For these curves, we also determine the necessary...
Using the Frobenius endomorphism the operation of computing scalar-mulitples in the Jacobian of a hyperelliptic curve is sped-up considerably. The kind of curves considered are Kobiltz i.e. subfield curves, defined over a small finite field which are then considered over a large extension field. We deal with computation of the group order over various extension fields, algorithms to obtain the mentioned speed-up, and experimental results concerning both issues. Additionally an alternative...
