ABSTRACT

In the last chapter, we introduced several number-theoretic problems-most prominently, factoring the product of two large primes and computing discrete logarithms in certain groups-that are widely believed to be hard. As defined there, this means there are presumed to be no polynomial-time algorithms for these problems. This asymptotic notion of hardness, however, tells us little about how to set the security parameter-sometimes called the key length, although the terms are not interchangeable-to achieve some desired, concrete level of security in practice. A proper understanding of this issue is extremely important for the real-world deployment of cryptosystems based on these problems. Setting the security parameter too low means a cryptosystem may be vulnerable to attacks more efficient than anticipated; being overly conservative and setting the security parameter too high will give good security, but at the expense of efficiency for the honest users. The relative difficulty of different number-theoretic problems can also play a role in determining which problems to use as the basis for building cryptosystems in the first place.