Cryptography Reference
In-Depth Information
functions, and we overviewed and discussed some functions that are conjectured to
be one way or trapdoor. More specifically, we looked at the discrete exponentiation
function, the RSA function, and the modular square function. We further looked
at hard-core predicates and algorithms for factoring integers or computing discrete
logarithms. Curiously, factoring integers and computing discrete logarithms seem
to have essentially the same difficulty (and computational complexity), at least as
indicated by the current state-of-the-art algorithms.
Most public key cryptosystems in use today are based on one (or several) of the
conjectured one-way functions mentioned earlier. This is also true for ECC, which
works in cyclic groups in which known special-purpose algorithms to compute dis-
crete logarithms do not work. From a practical viewpoint, ECC is interesting because
it allows us to use smaller keys (compared to other public key cryptosystems). This is
advantageous especially when it comes to implementing cryptographic systems and
applications in environments that are restricted in terms of computational resources
(e.g., smartcards). For the purpose of this topic, however, we don't make a major
distinction between public key cryptosystems that are based on the DLP and public
key cryptosystems that are based on the ECDLP.
In either case, it is sometimes recommended to use cryptosystems that com-
bine different candidate one-way functions in one way or another. If one of these
functions then turns out not to be one way, then the other functions still remain and
keep on securing the cryptosystem. Obviously, this strategy becomes useless if all
functions turn out not to be one way.
References
[1]
Pohlig, S., and M.E. Hellman, “An Improved Algorithm for Computing Logarithms over GF(p),”
IEEE Transactions on Information Theory , Vol. 24, January 1978, pp. 106-110.
[2]
Maurer, U.M., “Towards the Equivalence of Breaking the Diffie-Hellman Protocol and Com-
puting Discrete Logarithms,” Proceedings of CRYPTO '94 , Springer-Verlag, LNCS 839, 1994,
271-281.
[3]
Maurer, U.M., and S. Wolf, “The Diffie-Hellman Protocol,” Designs, Codes, and Cryptography ,
Special Issue on Public Key Cryptography, Vol. 19, No. 2-3, 2000, pp. 147-171.
[4]
Lenstra, H.W., “Factoring Integers with Elliptic Curves,” Annals of Mathematics , Vol. 126, 1987,
pp. 649-673.
[5]
Morrison, M.A., and J. Brillhart, “Method of Factoring and the Factorization of F 7 ,” Mathematics
of Computation , Vol. 29, 1975, pp. 183-205.
[6]
Pomerance, C., “The Quadratic Sieve Factoring Algorithm,” Proceedings of EUROCRYPT '84 ,
Springer-Verlag, 1984, pp. 169-182.
[7]
Lenstra, A.K., and H.W. Lenstra, The Development of the Number Field Sieve . Springer-Verlag,
LNCS 1554, New York, 1993.
Search WWH ::




Custom Search