CryptoDB
Thomas J. Wollinger
Publications
Year
Venue
Title
2008
EPRINT
Fast explicit formulae for genus 2 hyperelliptic curves using projective coordinates (Updated)
Abstract
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.
2005
EPRINT
Efficient Doubling on Genus 3 Curves over Binary Fields
Abstract
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 binary fields we investigate how to
compute faster doubling in this paper.
By constructing birational transformation of variables, we derive
explicit doubling formulae for all types of defining equations of
the curve. For each type of curve, we analyze how many field operations are needed. So far all proposed curves are secure,
though they are more special types. Our results allow to choose
curves from a large enough variety which have extremely fast
doubling needing only one third the time of an addition in the
best case. Furthermore, an actual implementation of the new formulae
on a Pentium-M processor shows its practical relevance.
2004
EPRINT
Finding Optimum Parallel Coprocessor Design for Genus 2 Hyperelliptic Curve Cryptosystems
Abstract
Hardware accelerators are often used in cryptographic
applications for speeding up the highly arithmetic-intensive
public-key primitives, e.g. in high-end smart cards. One of these
emerging and very promising public-key scheme is based on
HyperElliptic Curve Cryptosystems (HECC). In the open literature
only a few considerations deal with hardware implementation issues
of HECC.
Our contribution appears to be the first one to propose
architectures for the latest findings in efficient group
arithmetic on HEC. The group operation of HECC allows
parallelization at different levels: bit-level parallelization
(via different digit-sizes in multipliers) and arithmetic
operation-level parallelization (via replicated multipliers). We
investigate the trade-offs between both parallelization options
and identify speed and time-area optimized configurations. We
found that a coprocessor using a single multiplier (D = 8)
instead of two or more is best suited. This coprocessor is able to
compute group addition and doubling in 479 and 334 clock
cycles, respectively. Providing more resources it is possible to
achieve 288 and 248 clock cycles, respectively.
2003
EPRINT
Hyperelliptic Curve Cryptosystems: Closing the Performance Gap to Elliptic Curves (Update)
Abstract
For most of the time since they were proposed, it was widely
believed that hyperelliptic curve cryptosystems (HECC) carry a
substantial performance penalty compared to elliptic curve
cryptosystems (ECC) and are, thus, not too attractive for
practical applications. Only quite recently improvements have been
made, mainly restricted to curves of genus 2. The work at hand
advances the state-of-the-art considerably in several aspects.
First, we generalize and improve the closed formulae for the group
operation of genus 3 for HEC defined over fields of characteristic
two. For certain curves we achieve over 50% complexity improvement
compared to the best previously published results. Second, we
introduce a new complexity metric for ECC and HECC defined over
characteristic two fields which allow performance comparisons of
practical relevance. It can be shown that the HECC performance is
in the range of the performance of an ECC; for specific
parameters HECC can even possess a lower complexity than an ECC at
the same security level. Third, we describe the first
implementation of a HEC cryptosystem on an embedded (ARM7)
processor. Since HEC are particularly attractive for constrained
environments, such a case study should be of relevance.
2003
EPRINT
Low Cost Security: Explicit Formulae for Genus 4 Hyperelliptic Curves
Abstract
It is widely believed that genus four hyperelliptic curve
cryptosystems (HECC) are not attractive for practical applications
because of their complexity compared to systems based on lower
genera, especially elliptic curves. Our contribution shows that
for low cost security applications genus-4 hyperelliptic curves
(HEC) can outperform genus-2 HEC and that we can achieve a
performance similar to genus-3 HEC. Furthermore our implementation
results show that a genus-4 HECC is an alternative cryptosystem to
systems based on elliptic curves.
In the work at hand we present for the first time explicit
formulae for genus-4 HEC, resulting in a 60% speed-up compared to
the best published results. In addition we implemented genus-4
HECC on a Pentium4 and an ARM microprocessor. Our implementations
on the ARM show that for genus four HECC are only a factor of 1.66
slower than genus-2 curves considering group order ~2^{190}.
For the same group order ECC and genus-3 HECC are about
a factor of 2 faster than genus-4 curves on the ARM. The two most
surprising results are: 1) for low cost security application,
namely considering an underlying group of order 2^{128}, HECC
with genus 4 outperform genus-2 curves by a factor of 1.46 and has
similar performance to genus-3 curves on the ARM and 2) when
compared to genus-2 and genus-3, genus-4 HECC are better suited to
embedded microprocessors than to general purpose processors.
2003
EPRINT
How Secure Are FPGAs in Cryptographic Applications?
Abstract
The use of FPGAs for cryptographic applications is highly
attractive for a variety of reasons but at the same time there are
many open issues related to the general security of FPGAs. This
contribution attempts to provide a state-of-the-art description of
this topic. First, the advantages of reconfigurable hardware for
cryptographic applications are discussed from a systems
perspective. Second, potential security problems of FPGAs are
described in detail, followed by a proposal of a some
countermeasure. Third, a list of open research problems is
provided. Even though there have been many contributions dealing
with the algorithmic aspects of cryptographic schemes implemented
on FPGAs, this contribution appears to be the first comprehensive
treatment of system and security aspects.
2003
EPRINT
High Performance Arithmetic for Hyperelliptic Curve Cryptosystems of Genus Two
Abstract
Nowadays, there exists a manifold variety of cryptographic applications: from low level embedded crypto implementations up to high end cryptographic engines for servers. The latter require a flexible implementation of a variety of cryptographic primitives in order to be capable of communicating with several clients. On the other hand, on the client it only requires an implementation of one specific algorithm with fixed parameters such as a fixed field size or fixed curve parameters if using ECC/ HECC. In particular for embedded environments like PDAs or mobile communication devices, fixing these parameters can be crucial regarding speed and power consumption. In this contribution, we propose a highly efficient algorithm for a hyperelliptic curve cryptosystem of genus two, well suited for these constraint devices.
In recent years, a lot of effort was made to speed up arithmetic on genus-2 HEC. This work is based on the work of Lange and presents a major improvement of HECC arithmetic for curves defined over fields of characteristic two. We optimized the group doubling operation for certain types of genus-2 curves and we were able to reduce the number of required multiplications to a total of 9 multiplications. The saving in multiplications is 47% for the cost of one additional squaring. Thus, the efficiency of the whole cryptosystem was drastically increased.
Coauthors
- Guido Bertoni (1)
- Luca Breveglieri (1)
- Xinxin Fan (1)
- Jorge Guajardo (2)
- Vladislav Kovtun (1)
- Christof Paar (7)
- Jan Pelzl (4)
- Kai Schramm (1)
- Yumin Wang (1)