SCIENTIFIC PROGRAMS AND ACTIVITIES
|April 18, 2014|
Fields Institute Workshop on
Isabelle Déchène, University of Ottawa
Algebraic Groups: Computational Aspects and Cryptographic Applications
Abelian varieties, genus, Jacobians, divisors, Picard group, tori, Riemann-Roch, hyperelliptic curves are terms you all heard in one crypto talk or another. Still confused about the relations among them? If so, now is the time to roll-up your sleeves and get to the bottom of this.
Indeed, in order to make a step further and pursue "new directions in cryptography", it is sometimes wise to first get to know what is surrounding you. During this mini-course, we will sort out what's what in order to discuss and compare the cryptographic properties of chosen projective varieties and linear algebraic groups. We will then present an introduction to non-hyperelliptic curves and generalized Jacobians, two of the most recent ideas of this field.
The strength of a cryptographic algorithm has always been discussed in terms of its resistance to black-box attacks. As more and more security moves into the software world, this is an increasingly unrealistic model. In this talk, we discuss the much more realistic (and unfortunately, much more severe) white-box attack context. We will look at ongoing research on ways to have secure cryptography in this context, including cipher design that takes white-box attacks into account.
The last decade has witnessed a surge of scientific activity in designing secure systems that are responsive to rapid changes in technology. Missteps are being corrected, irregularities straightened, lessons learned and the world has never came to a halt. The next decade looks just as promising and penetrating studies will attempt to balance theory and practice. In this talk we peer into security's crystal ball and look at fundamental questions that may affect the many facets of research on this subject.
Scalar multiplication is the central and most time-consuming operation in many public-key curve-based systems such as Elliptic Curve (ECC), Hyperelliptic Curve (HECC) and Pairing-based cryptosystems. Its algorithmic and computational structure has been the focus of extensive research in recent years in a growing effort to reduce its time execution and power/memory requirements and, thus, to make the corresponding systems suitable for implementation in the myriad of new applications using devices such as PDAs, smartcards, cellphones, RFID tags and wireless sensor networks.
In this mini-course, we discuss various methodologies that we have developed to accelerate scalar multiplication on ECCs over prime fields, and show their impact in sequential and parallel implementations that also include protection against Simple Side-Channel Attacks (SSCA). We also present a new method for computation of scalar multiplication that uses a generic multibase representation to reduce the number of required operations.
This is joint work with Patrick Longa.
Considerable attention has been given recently to the construction of new hash functions. After reviewing some of this work, we shall present the function "ERINDALE" that has been developed in joint work with Nikolajs Volkovs of the GANITA Lab at the University of Toronto.
Elliptic Curve Cryptography (ECC) is a public key crypto system based upon a hard number theoretic problem: elliptic curve discrete logarithms. At the base of ECC curve operations is finite field (Galois Field) algebra with focus on prime Galois fields, GF(p), and binary extension Galois fields, GF(2^m). The performance of the ECC curve operations depend on the performance of the Galois field arithmetic, as well as the choice of point representation, and point addition/doubling formulae. Both prime and binary field types offer advantages and disadvantages in software and hardware based cryptosystems. These trade offs are described and analyzed in more detail in the present paper.
We give an overview of recent advances in the field of Identity-based Encryption (IBE). We will discuss schemes that enjoy security proofs in the standard model. We will also describe schemes that avoid the use of bilinear maps. Finally, we will identify open problems in IBE and connections between IBE and others areas of cryptography.
Algebraic geometers and cryptographers are very familiar with what the traditional "imaginary" model of a hyperelliptic curve. Another less familiar description of such a curve is the so-called "real" model; the terminology stems from the analogy to real and imaginary quadratic number fields. Structurally and arithmetically, the real model behaves quite differently from its imaginary counterpart. While divisor addition with subsequent reduction ("giant steps") is still essentially the same, the real model no longer allows for efficiently computable unique representation of elements in the Jacobian via reduced representatives. However, the real model exhibits a so-called infrastructure, with an additional much faster operation ("baby steps"). We present the real model of a hyperelliptic curve and its two-fold baby step giant step divisor arithmetic. We also indicate how to use these algorithms for potential cryptographic and number theoretic applications.
In elliptic curve cryptography, the costliest operation is the computation of nP=P+...+P, called scalar multiplication. It is acknowledged that the existence of fast endomorphisms (such as the Frobenius on Koblitz curves) results in clear performance speedup. I will expose how the use of double base expansions of n gives way to a new class of scalar multiplication algorithms capable of provably beating the fastest known implementations on Koblitz curves, with negligible additional memory.
There has been considerable recent interest in manual authentication protocols, where a Sender S and a Receiver R are connected by an insecure channel as well as a narrowband authenticated (i.e., a "manual") channel. S wishes to send a "long" message over the insecure channel, which is authenticated to R using a short authenticator sent over the manual channel. S and R are assumed to have have no shared secret key, nor is there is an infrastructure to support public-key cryptography. It is of interest to design protocols in this setting that are secure against an active adversary.
In this talk, we will discuss how manual authentication protocols can be designed and analyzed. We consider non-interactive as well as interactive schemes, and we look at both unconditionally secure prootcols and protocols that are provably secure in the random oracle model.
This talk is based on joint work with Atefeh Mashatan.
We discuss several methods that can be used to accelerate the verification step of ECC-based signature schemes. We show how to obtain a 40% efficiency improvement of ordinary ECDSA signature verification and even a factor 2.4x efficiency improvement when ECDSA certificate verification is combined with the key computation step in Diffie-Hellman-based protocols, such as static-ECDH and ECMQV. This challenges the conventional wisdom that with ECC-based signature schemes, signature verification is always considerably slower than signature generation and slower than RSA signature verification. Results apply to all prime curves standardized by NIST, the NSA 'Suite B' curves, and the so-called Brainpool curves.
The security of symmetric key primitives, such as block ciphers, stream ciphers and hash functions, depends on the cryptographic properties of the underlying Boolean functions. Cryptographic Boolean functions should satisfy several properties such as balance, high nonlinearity, high resiliency degree, and high algebraic immunity degree.
In this talk, we review different classes of Boolean functions of cryptographic interest. Then, we show how the generalizations of several earlier attacks on symmetric ciphers have led to the definition of new properties that can be used to ensure the ciphers' resistance against these attacks. We will also discuss the recently developed algebraic attacks and provide a brief summary of recent results related to the construction of Boolean functions with high algebraic immunity degree.