Project Highlights (2007)

• Workshops
  • Co-organized the 11th Annual Workshop on Elliptic Curve Cryptography at University College Dublin (Sep 5-7 2007). Sponsors included Certicom. The workshop was attended by 130 people.
  
  
• Students
  • In 2007, MITACS funds were used for partial support of three PDFs: Shaoquan Jiang (University of Calgary), Mridul Nandi (University of Waterloo), and Omran Ahmadi (University of Toronto).
  • MITACS funds were also used to support the research of graduate students Koray Karabina, Berkant Ustaoglu, Kayo Yoshida, and Edward Knapp (University of Waterloo).
  
  
• Research
  • Elliptic curve cryptography: Vassil Dimitrov and Michael Jacobson extended the double base ideas for exponentiation to tau-adic expansions for point multiplication on Koblitz elliptic curves. The algorithms lead to very efficient implementations of elliptic curve cryptosystems based on the Koblitz curves that have been recommended by NIST. The new algorithms were implemented in FPGA, confirming their efficiency.
    
    
  • Cryptography in hyperelliptic function fields: Michael Jacobson and Renate Scheidler (together with Andreas Stein) formulated and analyzed a new algorithm for computing the reduced sum of two divisors of an arbitrary hyperellipti curve. The formulations and algorithms are generalizations of Shanks's NUCOMP algorithm, which was suggested earlier for composing and reducing positive definite binary quadratic forms. The new formulation of NUCOMP is derived by approximating the irrational continued fraction expansion used to reduce a divisor by a rational continued fraction expansion, resulting in a relatively simple and efficient presentation of the algorithm as compared to previous version. Numerical data demonstrates that our version of NUCOMP is more efficient than Cantor's algorithm for most hyperelliptic curves, except those of very small genus defined over small finite fields.
    
    
  • Pairing-friendly elliptic curves: Elliptic curves with small embedding degree and large prime-order subgroup are key ingredients for implementing pairing-based cryptographic systems. Such "pairing-friendly" curves are rare and thus require specific constructions. Edlyn Teske (together with David Freeman and Mike Scott) devised a single coherent framework that encompasses all of the constructions currently existing in the literature. They also include new constructions of pairing-friendly elliptic curves that improve on the previously known constructions for certain embedding degrees. Finally, for all embedding degrees up to 50, they provided recommendations as to which pairing-friendly curves to choose to best satisfy a variety of performance and security requirements.
    
    
  • Ate pairing on hyperelliptic curves: Roger Oyono (together with R. Granger, F. Hess, N. Theriault and F. Vercauteren) showed that the Ate pairing, originally defined for elliptic curves, generalizes to hyperelliptic curves and in fact to arbitrary algebraic curves. The pairing has the following surprising properties: The loop length in Miller's algorithm can be up to $g$ times shorter that for the Tate pairing, with g the genus of the curve, and the pairing is also automatically reduced, that is no final exponentiation is needed. The new algorithms can be used to implementing pairing-based cryptographic protocols such as identity-based encryption schemes. The work was presented at EUROCRYPT 2007.
    
    
  • Security of cryptographic protocols: Berkant Ustaoglu devised an efficient key agreement protocol, combining features of the MQV, HMQV and NAXOS protocols. The protocol has a relatively simple reductionist security proof. Menezes and Ustaoglu formulated an appropriate security model and definition, and used it to provide a reductionist security proof for the "Unified Model" key agreement protocol that has been standardized by the US government's National Institute for Standards and Technology (NIST).
    
    
  • Cubic function fields: This is a long-term research initiative whose aim it is to analyze the structure as well as develop and implement fast algorithms for cubic function fields and number fields, with a special focus on investigating certain classes of cubic function fields for cryptographic applications. Recent results include first steps in an arithmetic framework and the development of tight bounds on the class number (the order of the Jacobian) of an arbitrary cubic function field, as well as a very efficient algorithm for determining the order of the Jacobian of a Picard curve. For the past three summers, teams of undergraduate research assistants have also designed computer code for this project under the direction of M. Bauer, M. Jacobson and R. Scheidler. The theoretical and arithmetic side of this project continues to be an active field of research that will also lead to several graduate theses.