ECC 2001
Speaker Dan Bleichenbacher Title On the generation of DSA one-time keys AbstractThis talk analyzes the digital signature algorithm (DSA). For each signature a secret random one-time key k _{j} has to be
generated. The standard proposes a method for generating these
one-time keys, which is biased.
I present a heuristic attack exploiting this bias. Given sufficiently many known signature it is possible to find the secret key significantly faster than with previously known algorithms. For example, the secret key can often be found given 2 ^{22} signatures
in time 2^{64} and with memory 2^{40}. The complexity of the attack
does not depend on the group size p.
SpeakerDaniel Brown TitleA security analysis of the elliptic curve digital signature algorithm AbstractIn January 2000, the National Institute of Standards & Technology (NIST) approved the Elliptic Curve Digital Signature Algorithm (ECDSA) for use by the U.S. Government through publication of the Federal Information Processing Standards document, FIPS 186-2. However, within the academic cryptographic community, no provable security analyses have been directed specifically at ECDSA - until now. We consider the security of ECDSA under a variety of assumptions, such as the collision-resistance of the Secure Hash Algorithm SHA-1 and the semi-generic group model of an elliptic curve group. We also consider a variety of adversarial goals, including existential forgery by an adaptive chosen-message attack. SpeakerGerhard Frey TitleAlgebraic-geometric discrete logarithms: An overview AbstractThe main task of public key cryptography is to provide highly efficient tools to exchange keys, sign electronic messages, authenticate members of a network and, sometimes, encrypt and decrypt messages by using simple protocols with clear and easy to follow implementation rules based on secure crypto primitives. It has turned out during the last 15 years that the discrete logarithm (DL) in groups of prime order can be used for these purposes. The systems used today are all constructed by arithmetical-geometrical methods as class groups of orders in number fields or function fields, and since these objects have been studied for 100 years and longer we can rely on a well understood mathematical background. The purpose of this lecture is explain the relevant constructions and to show how arithmetic geometry can be used in constructive and destructive ways. Especially it will turn out that Jacobian varieties of projective curves of small positive genus play a distinguished role with respect to shortness of keys, security, performance and key generation. This will explain why elliptic curves over prime fields or over fields of small characteristic and prime absolute degree are a very good choice for designing DL-systems. Speaker Pierrick Gaudry TitleAlgorithms for point counting on elliptic and hyperelliptic curves AbstractCounting points is a tricky task when implementing an elliptic or hyperelliptic cryptosystem. Even though random curves are thought to be the most secure ones, particular curves for which the number of points comes for free are still widely used. We will give a survey of the best methods known for point counting on random elliptic and hyperelliptic curves. These methods differ for curves defined over a prime field and curves in characteristic 2. We shall give an emphasis to the latter case, for which a lot of progress have been achieved recently, following Satoh's algorithm breakthrough. SpeakerDarrel Hankerson TitlePerformance comparisons of elliptic curve systems in software AbstractImplementing elliptic curve cryptographic schemes involves many design decisions including underlying field (prime, Mersenne-like prime, characteristic two, optimal extension), curve (randomly selected, Koblitz, Gallant), memory usage, and implementation language (C or assembler). We present and compare the results of our software implementation of these various flavours of elliptic (and hyperelliptic) curve systems. SpeakerFlorian Hess TitleAn extension of the GHS Weil descent attack AbstractThe GHS Weil descent attack maps an elliptic curve discrete logarithm problem in characteristic two to an equivalent discrete logarithm problem on a hyperelliptic curve over a smaller finite field. Under quite special conditions this later problem can be solved easier. In the talk we review the basic technique and present an extension which applies under less (but arguably still quite) special conditions. We also discuss some implications. SpeakerRaymond Laflamme TitleQuantum Computing AbstractAdvances in computing are revolutionizing our world. Present day computers advance at a rapid pace toward the barrier defined by the laws of quantum physics. The quantum computation program short-circuits that constraint by exploiting the quantum laws to advantage rather than regarding them as obstacles. Quantum computer accepts any superposition of its inputs as an input, and processes the components simultaneously, performing a sophisticated interference experiment of classical inputs. This ``quantum parallelism'' allows one to explore exponentially many trial solutions with relatively modest means, and to select the correct one. This has a particularly dramatic effect on factoring of large integers, which is at the core of the present day encryption strategies (public key) used in diplomatic communication, and (increasingly) in business. As demonstrated approximately five years ago, quantum computers could yield the most commonly used encryption protocol obsolete. Since then, it was also realized that quantum computation can lead to breakthroughs elsewhere, including simulations of quantum systems, implementation of novel encryption strategies (quantum cryptography), as well as more mundane applications such as sorting. I will describe recent work done in quantum computation, in particular the discovery and implementation of methods to make quantum information robust against corruption, both in theory and experiments. I will end with speculations about the field. SpeakerAlfred Menezes TitleCryptographic implications of Weil descent AbstractIn 1998, Frey proposed using Weil descent as a means to reduce the discrete logarithm problem in elliptic curves over characteristic two finite fields to the logarithm problem in abelian varieties over smaller underlying fields where subexponential-time methods may be applicable. In 2000, Gaudry, Hess and Smart showed how Frey's methodology could be used to reduce the ECDLP to the discrete logarithm problem in the Jacobian of a hyperelliptic curve. This talk will provide an overview of the Weil descent methodology and discuss its implications to the security of elliptic curve systems. SpeakerTatsuaki Okamoto TitleGeneric conversions for constructing IND-CCA2 public-key encryption in the random oracle model AbstractUntil a few years ago, the description of a cryptosystem, together with some heuristic arguments for security, were enough to convince and to make a scheme to be widely adopted. Formal semantic security and further non-malleability against active attacks were just seen as theoretical properties. However, after multiple cryptanalyses of international standards, provable security has been realized to be important and even became a basic requirement. Therefore, several practical cryptosystems with the formal security requirements in the strongest sense, IND-CCA2 (non-malleable/semantically secure against adaptively chosen-cipphertext attacks), have been proposed. In my talk, I will introduce several generic conversion methods from a weakly secure public-key encryption (PKE) primitive to an IND-CCA2 PKE scheme in the random oracle model (ROM). I will show some applications of these conversions to the ellitic curve (EC) ElGamal scheme. As another application, I will also mention RSA-REACT and its advantage over the RSA-OAEP families. In addition, I may talk about the relationship among computational, decisional, and gap (oracle) problems such as DH, decisional DH (DDH) and gap DH (GDH) problems. SpeakerAlice Silverberg TitleElliptic curves: The state of the art AbstractThis talk will give a survey of recent number-theoretical advances concerning elliptic curves. We will introduce some of the major open questions about elliptic curves from a number theorist's point of view, and discuss recent progress that has been made towards their solutions. The topics will include the Conjecture of Birch and Swinnerton-Dyer, and questions about distributions of ranks of elliptic curves. SpeakerBrian Snow TitleWe need more assurance in security products AbstractCommercial Security Systems, especially those provided in software, need to meet higher assurance standards than other typical commercial products do. Reasons for this assertion will be given, and a discussion of various ways to achieve it. Particular attention will be paid to Systems Engineering Techniques, Operating Systems, Software Modules, Hardware features, Third Party Validation, and Legal Constraints. SpeakerJerome A. Solinas TitleSome computational speedups and bandwith improvements for curves over prime fields AbstractWe present some new efficiency improvements for elliptic scalar multiplication. We begin with an optimized version of Shamir's method of evaluating expressions of the form $aP+bQ$. Not only is this expression commonly required in the execution of public-key protocols on elliptic curves, but it also provides faster methods of ordinary scalar multiplication. We present some curves for which this speedup is optimized. We also address the problem of minimizing the bandwidth required to specify the parameters for an elliptic curve. In particular, we present a family of curves whose parameter sets are ID-based. This enables the specification of parameters with little or no extra bandwidth. This family of curves is also well suited to the Shamir speedup. SpeakerAnnegret Weng TitleThe CM-method for hyperelliptic curves AbstractDetermining the group order of the Fp-rational points of a hyperelliptic Jacobian is a non-trivial problem. In our talk we give a generalization of the CM-method to hyperelliptic curves. The main idea is the construction of a Jacobian with given endomorphism ring. We present cryptographically interesting examples for genus two and three. |