Algorithms in Number Theory and Cryptography

数论和密码学算法

• 批准号: RGPIN-2022-03559
• 负责人: Jacobson, Jr, Michael
• 金额: $ 2.11万
• 依托单位: University of Calgary
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=749835
• 关键词: Algorithms; Number; Theory; 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.

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