Titles and abstracts:
-
Peter Birkner (Technische Universiteit Eindhoven, Netherlands)
Edwards Curves and the ECM Factorisation Method
The ECM method, introduced about 20 years ago by Lenstra, is one of the
best algorithms for factoring integers. This method employs elliptic
curves, usually in Montgomery form, to find a factor of a given integer.
The recently introduced Edwards and Twisted Edwards curves offer very
efficient arithmetic and can improve the speed of the ECM algorithm. We
give a brief overview of the ECM method and Edwards curves, and show how
to construct Edwards curves which are suitable for ECM, that is, Edwards
curves with large torsion and positive rank over Q.
- Daniel Brown (Certicom, Canada)
Elliptic Curve Hash (and Sign)
A hash function, inspired by Bellare and Micciancio's MuHASH, using
elliptic curve arithmetic will be presented. Though expected to be
slower than conventional hash functions, it is parallelizable and can
be made incremental, i.e. udpates to the middle of message are quick,
if some extra info is kept for this task. Its security is loosely
based on the established security of MuHASH. However, it differs from
MuHASH in not relying on pre-existing hash function as a random oracle
or as a collision-resistant function. In the generic group model, an
argument suggests the hash is collision resistant. (As a second
topic, the security of ECDSA will be shown to depend on two distinct
problems about the underlying EC group: the well-known discrete log
problem, and the poorly-known "one-up" problem.)
- Christophe Doche (Macquarie University, Australia)
Double-Base Number System and Applications
The Double-Base Number System (DBNS) is a way to represent any integer N
as Σli=1
± 2ai
3bi. The main interest of this system
is that it is very sparse. Indeed, it can be shown that the number of
terms needed to represent N is O(log N/log log N). It is a
fascinating area of research as it is linked to deep problems in number
theory, it is also very relevant to cryptography, especially regarding
exponentiation and scalar multiplication. That is why the DBNS has
attracted the interest of an increasing number of researchers since its
introduction by Dimitrov et al. during the 90s. In this talk, we summarize
the most recent developments. This includes a discussion of different
algorithms producing DBNS expansions and several generalizations, such as
the extended DBNS, DBNS for Koblitz curves and the Joint-DBNS. We will
also briefly discuss optimized triplings and other relevant operations
that make the DBNS suitable for scalar multiplications.
- Orr Dunkelman (Ecole Normale Superieure, France)
Hash Functions - Much ado about something
While other cryptographic primitives are sometimes idealized, the
ideal hash function, the random oracle, is often considered too strong
of a model. This follows from the fact that there are several security
properties related to hash functions, where each researcher picks the
ones that suit him or her the best. In this talk, we will cover the
various models, and the problems that recent results have identified
in the security of hash functions.
- Harold M. Edwards (Courant Institute of Mathematical Sciences, USA)
Abel's Generalization of the Addition Operation on Elliptic Curves
Niels Henrik Abel's great theorem of 1826 exercised a profound influence on
the subsequent development of mathematics in the fields of function theory,
Riemann surfaces, and algebraic geometry. Different mathematicians working
on different topics have formulated the theorem in so many different ways
that the question ``What is Abel's Theorem?'' has no easy answer. The talk
will address this question by viewing the theorem in the way that Abel
himself very probably did---as a natural generalization of the operation
of addition on an elliptic curve.
- Tim
Güneysu (Ruhr-University Bochum, Germany)
High Performance ECC over NIST Primes on Commercial FPGAs
Despite a wealth of research regarding high-speed software and
high-speed FPGA implementation of ECC since the mid 1990s, providing
truly high-performance ECC on readily available (i.e., non-ASIC)
platforms remains an open challenge. This holds especially for ECC over
prime fields, which are often preferred over binary fields due to
standards in Europe and the US, and a somewhat clearer patent situation.
We present a new architecture for an FPGA-based high performance ECC
implementation over prime fields. Our architecture makes intensive use
of the DSP blocks in modern FPGAs, which are embedded arithmetic units
actually intended to accelerate digitial signal processing algorithms.
We describe a novel parallel architecture and algorithms for performing
ECC arithmetic and describe the actual implementation of standard
compliant ECC based on the NIST primes P-224 and P-256.
- Antoine Joux (Universite de Versailles Saint-Quentin-en-Yvelines, France)
E-th roots and static Diffie-Hellman attacks using index calculus
Index calculus methods have been used succesfully for almost 30 years
to attack the number theoretic keystones of public key cryptography:
factoring and discrete logarithms. Currently, the fastest known
algorithms in the family are the number field sieve (NFS) and the
function field sieve (FFS). One or the other can be used against
factoring, discrete logarithm in fields of large or small
characteristic and discrete logarithm on some curves.
In this talk, we describe some new variations of index calculus
algorithms which no longer target the underlying number theory problem
(factoring or discrete logarithm) but instead focus on a related
cryptographic hard problem (computation of modular e-th roots or
static Diffie-Hellman problem). These new variations have better
complexity than their number theoretic counterparts.
- Timo Kasper (Ruhr-University Bochum, Germany)
On the Power of Power Analysis in the Real World
KeeLoq remote keyless entry systems are widely used for access control
purposes such as garage openers or car door systems. The talk will
present the first successful differential power analysis attacks on
numerous commercially available products employing KeeLoq code
hopping. They allow for efficiently revealing both the secret key of a
remote transmitter and the manufacturer key stored in a receiver. As a
result, a remote control can be cloned from only ten power traces,
allowing for a practical key recovery in few minutes. After extracting
the manufacturer key once, with similar techniques, it is possible to
recover the secret key of a remote control and replicate it from a
distance, just by eavesdropping on at most two messages. This
key-cloning without physical access to the device has serious
real-world security implications, as the technically challenging part
can be outsourced to specialists. During the talk, the attack will be
practically performed. Finally, it will be shown how to take over
control of a KeeLoq access control system, i.e., lock out an
legitimate user while the attacker may still open the door.
- Hyang-Sook Lee (Ewha Womans University, Seoul, Korea)
Efficient and Generalized Pairing Computation on Abelian Varieties
In this talk, we briefly survey the variants of Tate pairing for the
efficient pairing computation. In particular, we propose a new method
for constructing a bilinear pairing over (hyper)elliptic curves, which
we call the R-ate pairing. This pairing is a generalization of
the Ate and Atei pairing, and also improves efficiency of
the pairing computation. Using the R-ate pairing, the loop length in
Miller's algorithm can be as small as
log(r1/φ(k)) for some pairing-friendly elliptic
curves which have not reached this lower bound. On supersingular
hyperelliptic curves of genus 2, we also show that this approach makes
the loop length in Miller's algorithm shorter than that of the Ate
pairing. The result regarding the R-ate pairing is the joint work with
Eunjeong Lee (KIAS) and Cheol-Min Park (Ewha Womans University).
-
Elisabeth Oswald (University of Bristol, UK)
Advances in Power Analysis Attacks
Since the advent of power analysis attacks, researchers have
set out to investigate different attack techniques, attack
different algorithms and devices, and find (formal)
ways to describe and analyse their findings. In this talk,
I will review some of the results of the last 2-3 years made
in these areas.
-
Reza Rezaeian Farashahi (Technische Universiteit Eindhoven, Netherlands)
Binary Edwards Curves
Edwards curves have presented remarkably symmetric new forms of elliptic
curves, which have led to strongly symmetric addition laws in terms of
the coordinates of the points. We present "binary Edwards curves", which
are the new forms for ordinary elliptic curves over fields of
characteristic 2. Using these new forms, we present the first complete
addition formulas for binary elliptic curves.
The complete binary Edwards curves cover all isomorphism classes of
ordinary elliptic curves over F2n for n>2.
We also present the doubling formulas for binary Edwards curves, which
are extremely fast. Moreover, they are the first complete doubling
formulas in the literature. Finally, we describe complete formulas for
differential addition. These formulas propose extremely fast
differential-addition for binary elliptic curves.
- Éric Schost (University of Western Ontario, Canada)
Point counting in genus 2: reaching 128 bits
Genus 2 cryptosystems are now seen to become competitive with, or
faster than, their elliptic analogues, for a similar level of
security. One of the last missing steps is the determination of a
suitable, secure curve over a prime field of size about 2^128.
I will describe recent work with Pierrick Gaudry that led to a first
point count in this size, and review some of the underlying
algorithms, from factorization in high degree extensions to the
use of homotopy continuation techniques.
- Mike Scott (Dublin City University, Ireland)
New record breaking implementations of ECC on quadratic extensions using
endomorphisms
Recently a new method for doing ECC over quadratic extensions has been
proposed, which seems to be faster than standard methods over prime fields,
in part because a nice endomorphism can be exploited. Here we describe the
new method (which builds on earlier work by some Japanese researchers), and
describe implementations on both a small 8-bit micro-processor and on a
standard 64-bit workstation. Implementation issues and challenges are
addressed, and some possible extensions are described.
- Peter Stevenhagen (Universiteit Leiden, Netherlands)
Constructing abelian varieties for cryptographic use
Cryptography makes use of abelian varieties, mostly
elliptic curves and Jacobians of hyperelliptic curves,
that are defined over finite fields and have desirable
properties concerning their group orders and their
associated pairings.
In many cases, such abelian varieties can be constructed
from appropriate Weil-numbers using complex multiplication
techniques.
We explain how to find and use such Weil-numbers in
low-dimensional situations.
- Andrew V. Sutherland (Massachusetts Institute of Technology, USA)
Computing Hilbert class polynomials with the CRT method
The Hilbert class polynomial HD plays a key role in the
CM-method for
constructing elliptic curves of known order. In their recent award-winning
paper, Belding, Broker, Enge, and Lauter present an algorithm to compute
HD using the Chinese Remainder Theorem (CRT). Unlike
previous
CRT-based approaches, the complexity of their algorithm is comparable to
the best methods known, but they find its practical performance remains
inferior. We show that this need not be the case, presenting a number
of improvements that allow us to handle much larger values of D.
We apply these results to construct pairing-friendly elliptic curves of
prime order using |D| up to 1012, surpassing previous
records held by the complex analytic method.