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

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

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.***