SGER: Concrete Complexity of Number-Theoretic Problems of Importance to Cryptography

SGER：对密码学重要的数论问题的具体复杂性

• 批准号: 9712109
• 负责人: Rene Peralta
• 金额: $ 4.98万
• 依托单位: University of Wisconsin-Milwaukee
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-06-01 至 1998-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9712109&HistoricalAwards=false
• 关键词: SGER; Concrete; Complexity; Number; Theoretic

Modern cryptography relies heavily on assumptions about the asymptotic intractability of certain number-theoretic problems. However, at the implementation level, assumptions about the concrete complexity of problems of a fixed size must be made (e.g. the intractability of factorization assumption in practice is "factoring 1024-bit cryptographic numbers is impossible"). Determining what "small-size" is too small to be secure is the focus of this project: to design and implement algorithms which solve, in practice, those number-theoretic problems which are the pillars of modern cryptography. These problems which are vital to modern cryptography are i) the discrete logarithm problem; ii) deciding quadratic residuosity modulo a composite number; iii) factorization of cryptographic numbers. These three problems will be central to this project. The project will also consider a host of problems peripheral to these three: primality testing, fast arithmetric with large numbers, diophantine approximation, rapid factorization of small numbers, factorization of random numbers, and other problems that will surely arise as research progresses.***

现代密码学在很大程度上依赖于对某些数论问题的渐近难解性的假设。然而，在实现层面，必须对固定大小的问题的具体复杂性做出假设（例如，在实践中，因子分解假设的棘手性是“因子分解1024位密码数是不可能的”）。 确定什么是“小尺寸”太小而不安全是这个项目的重点：设计和实现算法，在实践中解决那些数论问题，这些问题是现代密码学的支柱。 这些对现代密码学至关重要的问题是：i）离散对数问题; ii）确定模合数的二次剩余; iii）密码数的因子分解。 这三个问题将是这个项目的核心。 该项目还将考虑许多与这三个问题无关的问题：素数测试，大数快速算术，丢番图近似，小数的快速因式分解，随机数的因式分解，以及随着研究的进展肯定会出现的其他问题。