Algorithms in Number Theory and Cryptography

点击翻译按钮获取中文摘要

Cryptography, the study of protecting data from unauthorized access, is an increasingly important concern in our society. As our personal information is widely available through the Internet, the need to protect and authenticate data is more imperative than ever. The security of many methods in modern public-key cryptography relies on the supposed difficulty of computational problems in mathematics and, in particular, number theory. These schemes are set up in such a way that presumably the only way for an attacker to break the given system is to solve an instance of one such problem. Although novel cryptographic applications continue to be developed, few number-theoretic problems are widely accepted as foundations for secure public-key protocols. Furthermore, most of these problems have strong theoretical relationships. In many cases, being able to solve one efficiently implies the ability to solve another efficiently as well, as has been demonstrated (for example) by algorithms for quantum computers. In other words, one dramatic mathematical discovery, or the development of a large-scale quantum computer, would render many current public-key cryptographic techniques insecure, undermining the security and trust in our digital systems that we all take for granted. Hard problems are rarely proved to be secure - in practice, years of focused scrutiny are needed before they are deemed to be ready for practical use. I intend to perform such scrutiny on problems in algebraic number theory and algebraic geometry via a program of improving algorithms and conducting numerical investigations in order to advance our overall knowledge of these settings. This will include four interconnected lines of inquiry, all of which build on my team's work and involve HQP at all levels: improving the efficiency of algorithms for computing with the basic objects of interest, studying algorithmically the difficulty of the supposed hard problems, applying these results to assess the efficiency and security of cryptosystems, and again applying these results to conduct numerical investigations of unproven conjectures about the associated algebraic number theoretic objects. Although these topics have been studied since the time of Gauss, there is still much that is unknown in terms of even basic arithmetic properties and the efficiency of algorithms for fundamental problems. The advances obtained through my research program will provide other investigators with a firmer foundation of well-understood and quantified performance characteristics and trade-offs on which to base their assessments of related cryptographic protocols. Canadian security agencies and companies will be able to use these results to better inform their decisions on security policy, and the trainees working on these projects will develop valuable skills in information security, computing, and mathematics for future employment in both the private and public sectors.