# Number Theory Inspired by Cryptography (05w5021)

Arriving in Banff, Alberta Saturday, November 5 and departing Thursday November 10, 2005

## Organizers

David Boyd (University of British Columbia)

Carl Pomerance (Dartmouth College)

Igor Shparlinski (University of New South Wales)

Hugh Williams (University of Calgary)

## Objectives

The main objective of this workshop is to bring together 35-40 of the most active and productive researchers in number theory and cryptography, especially those with expertise in computational number theory, who are eager to share their expertise and are open to working on new topics. We also expect that the cryptographers will bring new problems and ideas to the number theoretic community. Developments in both number theory and cryptography are both numerous and rapid; however, it is often the case that lack of contacts and communication between cryptographers and number theorists present obstacles in achieving significant advances on both sides. We hope to overcome these obstacles and foster new links between both areas.

Besides the formal program with scheduled talks, there will be plenty of time for informal discussions, which are more suited to the exchange of ideas that are still in ``mid-air'' and cannot be put on paper, but which could eventually become very fruitful.

We do not plan to publish any proceedings but we hope to be able to make slides of most of the talks available on the Internet for a greater community of researchers.

We certainly have very specific topics which this workshop will target. While the number of these topics might suggest a lack of unity of our objectives, it is important to realize that there is considerable interaction among these areas of investigation. In fact, these are simply different avenues of approach to the study of the major problems of number

different avenues of approach to the study of the major problems of number theoretic based cryptography.

Studying the distribution of smooth numbers. This is related to several important algorithms, such as the integer factorization, primality testing and discrete logarithm problems. Less known applications involve attacks on padded RSA signature schemes and on the ElGamal cryptosystem.

Studying the structure of the groups of points on elliptic curves. This is important for a better understanding of the present and future potential of elliptic curve cryptography. The same questions concerning class groups of hyperelliptic curves are of great interest as well. Certainly, finding new classes of cryptographically strong (or identifying new types of cryptographically weak) curves is of great importance and interest.

Studying the structure of class groups of algebraic number fields. In particular, quadratic fields provide very interesting structures where an analogue of the Diffie-Hellman protocol can be executed. This area definitely requires more attention from both mathematicians and practical cryptographers.

Studying multidimensional geometric lattices associated with cryptographic constructions. Typically it is expected that such lattices behave as ``random'' lattices and thus this argument is used to justify the success of the LLL algorithm when applied to such lattices. The underlying philosophy is: ``the vector which we want to find is much shorter than it is usually expected for a lattice of this volume, thus it is very unlikely that there is another nonparallel vector of similar length; thus, LLL should find the desired vector.'' Rigorous justification of this principle typically leads to new and interesting number theoretic questions and the study of systems of equations in finite rings and fields.

Bounds of new exponential sums involving functions of cryptographic interest. Such bounds may lead to proving expected pseudorandomness properties of various cryptographic primitives, which can be reformulated in terms of the statistical distance, accepted in cryptology.

Studying smooth values occurring among the orders of various groups of cryptographic interest. It is known that ``smooth'' group orders must be avoided, however the area is lacking rigorous results confirming that this can be achieved.

Studying the distribution of various types of polynomials over finite fields. In particular, this involves obtaining sharp bounds on the number of smooth polynomials and is important for the discrete logarithm problem. Certainly, results of at least the same level of precision as for the integers should be expected. Moreover, for polynomials over finite fields, the celebrated Weil result provides a rigorous version of the Riemann Hypothesis and thus one can actually anticipate stronger results.

Computational challenges arising in algorithmic number theory and cryptography. There is an on-going quest for developing new algorithms and making existing algorithms faster, more portable and better suited to current hardware and software. Parallelism is a new trend in this area as well. Recently there have been remarkable achievements in several benchmarking problems, such as integer factorization and computing discrete logarithms.

Investigation of many of these topics is still very much in its infancy; thus, a meeting involving several of the world's experts in this rapidly developing area of research is both timely and of great potential significance to the science of secure communication. This workshop will be quite different from any other cryptographic meeting currently being planned, as it will be small, tightly focused, and very mathematically oriented. We will invite several experts in the above areas, including both number theorists and cryptographers, who will be able to give an exhaustive account of the state of the art and feasible (as well as infeasible) further directions for research. We believe that the workshop will also provide a significant learning experience and exposure to current ideas and trends to younger researchers the early stages of their careers. Ultimately, we expect that this workshop will lead to new important results and publications.

We should also emphasize that this meeting fits in very well with the PIMS Period of Concentration in Number Theory for 2003-2005. So far, four BIRS Workshops involving number theory are either in the planning stage or have already taken place. This proposal is quite separate from all of them, but nicely complements the meeting on Explicit Methods in Number Theory planned

already taken place. This proposal is quite separate from all of them, but nicely complements the meeting on Explicit Methods in Number Theory planned for November of 2004. Furthermore, our emphasis on number theory as it relates to cryptography, with particular concentration on the topics described earlier, ensures that there will be little overlap between the two meetings. Certainly, the two participant lists are quite different.

Besides the formal program with scheduled talks, there will be plenty of time for informal discussions, which are more suited to the exchange of ideas that are still in ``mid-air'' and cannot be put on paper, but which could eventually become very fruitful.

We do not plan to publish any proceedings but we hope to be able to make slides of most of the talks available on the Internet for a greater community of researchers.

We certainly have very specific topics which this workshop will target. While the number of these topics might suggest a lack of unity of our objectives, it is important to realize that there is considerable interaction among these areas of investigation. In fact, these are simply different avenues of approach to the study of the major problems of number

different avenues of approach to the study of the major problems of number theoretic based cryptography.

Studying the distribution of smooth numbers. This is related to several important algorithms, such as the integer factorization, primality testing and discrete logarithm problems. Less known applications involve attacks on padded RSA signature schemes and on the ElGamal cryptosystem.

Studying the structure of the groups of points on elliptic curves. This is important for a better understanding of the present and future potential of elliptic curve cryptography. The same questions concerning class groups of hyperelliptic curves are of great interest as well. Certainly, finding new classes of cryptographically strong (or identifying new types of cryptographically weak) curves is of great importance and interest.

Studying the structure of class groups of algebraic number fields. In particular, quadratic fields provide very interesting structures where an analogue of the Diffie-Hellman protocol can be executed. This area definitely requires more attention from both mathematicians and practical cryptographers.

Studying multidimensional geometric lattices associated with cryptographic constructions. Typically it is expected that such lattices behave as ``random'' lattices and thus this argument is used to justify the success of the LLL algorithm when applied to such lattices. The underlying philosophy is: ``the vector which we want to find is much shorter than it is usually expected for a lattice of this volume, thus it is very unlikely that there is another nonparallel vector of similar length; thus, LLL should find the desired vector.'' Rigorous justification of this principle typically leads to new and interesting number theoretic questions and the study of systems of equations in finite rings and fields.

Bounds of new exponential sums involving functions of cryptographic interest. Such bounds may lead to proving expected pseudorandomness properties of various cryptographic primitives, which can be reformulated in terms of the statistical distance, accepted in cryptology.

Studying smooth values occurring among the orders of various groups of cryptographic interest. It is known that ``smooth'' group orders must be avoided, however the area is lacking rigorous results confirming that this can be achieved.

Studying the distribution of various types of polynomials over finite fields. In particular, this involves obtaining sharp bounds on the number of smooth polynomials and is important for the discrete logarithm problem. Certainly, results of at least the same level of precision as for the integers should be expected. Moreover, for polynomials over finite fields, the celebrated Weil result provides a rigorous version of the Riemann Hypothesis and thus one can actually anticipate stronger results.

Computational challenges arising in algorithmic number theory and cryptography. There is an on-going quest for developing new algorithms and making existing algorithms faster, more portable and better suited to current hardware and software. Parallelism is a new trend in this area as well. Recently there have been remarkable achievements in several benchmarking problems, such as integer factorization and computing discrete logarithms.

Investigation of many of these topics is still very much in its infancy; thus, a meeting involving several of the world's experts in this rapidly developing area of research is both timely and of great potential significance to the science of secure communication. This workshop will be quite different from any other cryptographic meeting currently being planned, as it will be small, tightly focused, and very mathematically oriented. We will invite several experts in the above areas, including both number theorists and cryptographers, who will be able to give an exhaustive account of the state of the art and feasible (as well as infeasible) further directions for research. We believe that the workshop will also provide a significant learning experience and exposure to current ideas and trends to younger researchers the early stages of their careers. Ultimately, we expect that this workshop will lead to new important results and publications.

We should also emphasize that this meeting fits in very well with the PIMS Period of Concentration in Number Theory for 2003-2005. So far, four BIRS Workshops involving number theory are either in the planning stage or have already taken place. This proposal is quite separate from all of them, but nicely complements the meeting on Explicit Methods in Number Theory planned

already taken place. This proposal is quite separate from all of them, but nicely complements the meeting on Explicit Methods in Number Theory planned for November of 2004. Furthermore, our emphasis on number theory as it relates to cryptography, with particular concentration on the topics described earlier, ensures that there will be little overlap between the two meetings. Certainly, the two participant lists are quite different.