University of Calgary

# Mathematical Foundations of Cryptographic Algorithms

Mathematics provides the foundation for much of cryptography. Shannon’s mathematical foundation of secrecy systems relies on probability theory and analysis of cipher systems from early times heavily draws on statistical methods. Since the late 1970s, cryptography has been closely connected to number theory. Many modern day public key cryptosystems make use of arithmetic in number theoretic structures. Moreover, the security of these schemes is frequently based on the presumed difficulty of a number theoretic problem. Construction of systems with information theoretic security uses combinatorial structures and algebraic codes as the main techniques, and mathematical models and proofs form foundation of today's provable security.

## Number Theoretic Foundations

Number theory offers a framework for many cryptographic systems and provides most of the hard computational problems used to provide security for these schemes. Finite fields, algebraic curves, and number fields serve as the basis for much of public key cryptography. For example, the security of the well-known RSA system is based on the difficulty of factoring a large integer. Most key agreement protocols rely on the difficulty of a class of number theoretic problems generally combined under the term discrete logarithm problem (DLP).

Researchers at ISPIA explore number theoretic structures that can serve as the basis for cryptographic schemes. Our investigations focus on class groups and infrastructures of global fields (algebraic number field and function fields) as well as Jacobians of algebraic curves. Our research not only contributes to a better understanding to the DLP in these mathematical settings, but is also of mathematical interest in its own right.

## Algorithms and Implementation

The efficiency of many public key cryptosystems relies on the speed of the arithmetic in various algebraic structures, such as exponentiation in a finite field or adding points on an elliptic curve. Thus, in addition to investigating efficiency improvements to cryptographic schemes themselves, it is important to work towards improving the speed of the underlying arithmetic operations. Furthermore, the same arithmetic is used in algorithms for solving problems arising in computational number theory, including discrete logarithm problems.

At ISPIA, our focus is on algorithms for fast arithmetic of divisors on algebraic curves and ideals in global fields, finding invariants of global fields (e.g., regulators, class numbers) and extracting discrete logarithms in various number theoretic settings. This research includes theoretical foundations, algorithm design and analysis, and computer implementation. Much of our work in this area focuses on algorithmic improvements that are verified using highly-optimized software simulations. In addition, we partner with the University of Calgary's Advanced Technology Information Processing Systems (ATIPS) Laboratory, whose members are involved in designing and building cryptographic custom hardware platforms.