Template of MITACS Project Website

Information is recognized by many organizations as an important asset. Few businesses could function effectively without the ability to rely to some extent on information as a resource. Information security is concerned with providing assurances about the security and authenticity of data, and is of strategic importance to todays world of open networks and electronic data. Privacy is a growing issue in the area of both wired and wireless technology. Consumers are becoming increasingly aware of their privacy rights and needs, and are demanding the ability to control the use of their data. In practice, privacy can be provided by a combination of legislative, policy, and technological means. This project has two main themes. The first is the exploration, together with representatives from industry and provincial and federal government agencies, of policy and technological aspects of privacy. The second is the design and analysis of number-theoretic solutions for solving problems involving privacy and information security.

1. Privacy. In the past few years, those involved in developing and implementing technology have experienced a growing awareness of privacy risks within those technologies and a better understanding of privacy-averse environments. This awareness has brought to the fore the need to develop and implement further technologies that are privacy protective. Parallel to this, around the globe, economic crime units and law enforcement agencies, governments, businesses and lawyers wrestle with the tools to combat the international specter of cyber crime and terrorism, while often sidelining key privacy issues. The exploration of privacy and security issues is fundamental to understanding how the construction and implementation of privacy policies and technologies can be improved for the real world. We will explore these and other privacy and security issues through a series of workshops designed to maximize interaction between key representatives from industry, academia, and government.

2. Number-Theoretic Cryptography. The security of most public-key cryptographic systems is based on the difficulty of a number-theoretic problem, such as the integer factorization problem of the discrete logarithm problem. Cryptosystems based on the difficulty of these problems are used commercially to secure electronic palyment over the Internet, stock trading from pagers and cell phones, and multi-applications on smart cards. We will continue to study important number-theoretic objects used in public-key cryptography. In particular, this includes elliptic curves, hyperelliptic curves, cubic curves, quadratic number fields, algebraic functions fields, finite fields, and integer lattices.

SUB-PROJECTS

1. Elliptic curve cryptography. We will continue to study the security of the elliptic curve discrete logarithm problem (ECDLP), the efficiency of elliptic curve systems, and the design and analysis of elliptic curve cryptographic protocols. We will also consider the analogues of these problems to other curves, including hyperelliptic curves, superelliptic curves, and Cab curves.

2. Cubic function fields. We intend to focus on developing and implementing algorithms for computing invariants of cubic function fields as well as exploring these fields for cryptographic applications. We have already developed an algorithm for computing the fundamental units and the regulator of a purely cubic function field of unit rank two. Work on generalizing ths technique to arbitary cubic fields is in progress. In a recengly published paper, Dr. Scheidler described a fast arithmetic in the ideal class group of a purely cubic function. In collaboration with Mark Bauer of the University of Waterloo, she is currently investigating improvements in speed to these algorithms, with special emphasis on fields of low genus, to make them practical for cryptographic purposes.

3. Real quadratic field cryptosystems. Although function fields as a basis for cryptography have several advantages over number fields, such as greater speed and cleaner computer implementation, it should be pointed out from an algorithmic and cryptographic perspective, they are less well understood than number fields. We intend to investigate algorithms for implementing key exchange protocols and for solving the discrete logarithm problem in real quadratic fields. We will be conducting this research in several areas: improved implementation, improved algorithm for solving the DLP, and Benchmarking.

4. Determination of optimal discriminants. One advantage to using number fields for cryptographic purposes is that we have some freedom in selecting a certain parameter, the discriminant. However, this parameter needs to be chosen optimally with respect to both security and efficiency of implementation. We are currently developing a low cost, high-speed special computing device called a number sieve to help determine optimal selections. In the case of real quadratic fields, attempts by adversaries to break the corresponding cryptographic scheme can be thwarted by selecting discriminants that are quadratic nonresidues for many of the smallest primes. We were able to use the fastest number sieve in existence, constructed in 1995 at the University of Manitoba, to show that finding such discriminants can be done very quickly. We are now using more modern Field Programmable Gate Array (FPGA) technology to build a faster and more flexible number sieve that can be tailored to a specific sieve problem instance. Although no hardware development is required for the new sieve, at least a year of full-time development work remains. The project is a collaborative effort involving Dr. Hugh Williams, MSc student Kjell Wooding, and Dr. C. Patterson of Xilinx (Boulder, Colorado).

5. Benchmarking. We will use a Beowulf cluster built of off-the-shelf components as the hardware configuration for the testing. A Beowulf cluster is a collection of individual stand-alone processors connected together so they can communicate. The servers will be interconnected with standard fast Ethernet connections and provide the computer power needed for the sieving part of the DLP algorithm. All software required for the cluster, including the operating system Linux, is free of charge when used for research purposes. The cluster is sufficiently flexible that it can be used to test the effectiveness of many other cryptosystems and can be used well beyond the lifetime of this project. Dr. Williams successfully applied to the Alberta Ingenuity Fund for $262,740 to set up this laboratory of high speed computing devices to test and benchmark cryptographic systems. We have recently combined this award with Professor Mike Jacobson's $642,000 CFI award to create a very extensive, powerful and dedicated system, which we expect to have up and running early in 2003.

6. Unconditional determination of the regulator. Another important consideration in our work is the question of whether a given instance of the DLP is actually solvable, which highlights the problem of testing an ideal for principality. To do this we need to know the regulator. Unfortunately, the regulator that the fastest algorithm currently available determines is conditional on the Generalized Riemann Hypothesis. It is of great interest to find the regulator unconditionally. The conditional algorithm should at least compute an integral multiple of the regulator, and this is something that can be checked very quickly. Having made this determination, the next problem is to establish that the integral multiplier of the regulator in the conditional regulator is 1. There are two phases of doing this. The first is to establish that the regulator must exceed some predetermined bound. The next is to prove that for no integer less than a certain amount can we have the regulator being conditional one divided byshould allow us to compute regulators for fields of perhaps 60 or 65 digit discriminants.