Algorithms in number theory and cryptography

数论和密码学中的算法

• 批准号: 238981-2011
• 负责人: Jacobson, Jr, Michael
• 金额: $ 2.4万
• 依托单位: University of Calgary
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=570538
• 关键词: Algorithms; number; theory; cryptography

In the past few decades, cryptography, the study of data security, has emerged as an important concern in our society. As information becomes increasingly accessible 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 certain 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. Currently, only three number-theoretic problems are widely accepted as foundations for secure public-key protocols. Furthermore, these three problems have strong theoretical relationships. In many cases, being able to solve one efficiently implies the ability to solve the other two efficiently as well. In other words, one dramatic mathematical discovery could render many current public-key cryptographic techniques insecure. I intend to investigate the suitability of certain problems in algebraic number theory as alternatives for public-key cryptography. This will involve improving the efficiency of algorithms for computing with the basic objects of interest, studying theoretically and algorithmically the difficulty of the supposed hard problems, and conducting general investigations into the associated algebraic number theoretic objects. For example, there are a number of extremely difficult computational problems in this area that have been proposed for cryptographic applications, but much more investigation is needed in terms of their security and efficiency. By attempting to devise new, more efficient methods to solve these problems, I will provide other researchers with a much firmer foundation on which to base their assessments of these cryptographic protocols. The end result will be a suite of well-understood, secure, and efficient cryptographic protocols that can be used to protect Internet communications, even if currently-used protocols are found to be insecure.

在过去的几十年里，研究数据安全的密码学已经成为我们社会关注的一个重要问题。随着信息越来越多地通过互联网访问，保护和验证数据的需求比以往任何时候都更加迫切。现代公钥密码学中许多方法的安全性依赖于数学中某些计算问题的假定难度，尤其是数论。这些方案的设置方式可能使攻击者破坏给定系统的唯一方法是解决一个此类问题的实例。目前，只有三个数论问题被广泛接受为安全公钥协议的基础。此外，这三个问题具有很强的理论关联性。在许多情况下，能够有效地解决一个问题意味着也能够有效地解决另外两个问题。换句话说，一项戏剧性的数学发现可能会使许多当前的公钥密码技术变得不安全。 我打算调查代数数论中的某些问题作为公钥密码学的替代方案的适用性。这将包括提高算法对基本感兴趣对象的计算效率，从理论和算法上研究假设的困难问题的难度，以及对相关的代数数论对象进行一般调查。例如，在这一领域中有许多非常困难的计算问题被提出用于密码应用，但在安全性和效率方面还需要更多的研究。通过尝试设计新的、更有效的方法来解决这些问题，我将为其他研究人员提供更坚实的基础，以便他们评估这些加密协议。最终结果将是一套易于理解、安全和高效的加密协议，即使当前使用的协议被发现是不安全的，这些协议也可以用于保护互联网通信。