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

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Type
Standard Grant (Standard)
Application #
9712109
Program Officer
Yechezkel Zalcstein
Project Start
Project End
Budget Start
1997-06-01
Budget End
1998-05-31
Support Year
Fiscal Year
1997
Total Cost
$49,807
Indirect Cost
Name
University of Wisconsin Milwaukee
Department
Type
DUNS #
City
Milwaukee
State
WI
Country
United States
Zip Code
53201