Algorithms in Number Theory and Cryptography

密码学是一门研究保护数据免受未经授权访问的学科，在我们的社会中越来越受到关注。由于我们的个人信息可以通过互联网广泛获取，保护和验证数据的需求比以往任何时候都更加迫切。现代公钥密码学中许多方法的安全性依赖于数学，特别是数论中计算问题的假定难度。这些方案的设置方式假定攻击者破坏给定系统的唯一方法是解决此类问题的一个实例。尽管新的密码学应用不断发展，但很少有数论问题被广泛接受为安全公钥协议的基础。此外，这些问题大多具有很强的理论关系。在许多情况下，能够有效地解决一个问题意味着能够有效地解决另一个问题，正如（例如）量子计算机的算法所证明的那样。换句话说，一个戏剧性的数学发现，或者大型量子计算机的开发，将使许多当前的公钥加密技术变得不安全，破坏我们对数字系统的安全性和信任，而我们都认为这是理所当然的。难题很少被证明是安全的——在实践中，在它们被认为准备好实际应用之前，需要多年的集中审查。我打算对代数数论和代数几何中的问题进行这样的仔细研究，通过一个改进算法和进行数值研究的计划，以提高我们对这些设置的整体知识。这将包括四个相互关联的调查线，所有这些都建立在我的团队的工作基础上，并涉及各级HQP：提高基本目标计算算法的效率，从算法上研究假定困难问题的难度，应用这些结果来评估密码系统的效率和安全性，并再次应用这些结果对相关代数数论对象的未证明猜想进行数值研究。虽然这些主题自高斯时代以来一直在研究，但就基本的算术性质和基本问题的算法效率而言，仍然有许多未知的东西。通过我的研究项目获得的进展将为其他研究人员提供一个更坚实的基础，使他们能够很好地理解和量化性能特征和权衡，并以此为基础评估相关的加密协议。加拿大的安全机构和公司将能够利用这些结果更好地为他们的安全政策决策提供信息，参与这些项目的学员将在信息安全、计算和数学方面培养宝贵的技能，为未来在私营和公共部门的就业做好准备。

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.