DIMACS Special Year on Networks Seminar


Lower Bounds for Discrete Logarithms and Related Problems


Victor Shoup


AT&T Murray Hill Building, Room: 2A-435
Note: Visitors not from the MH building should use the east side entrance "stairway 9", and call Dahlia Malkhi, phone number 7809, to let them in. Since entering the MH building takes time, vistors are requested to arrive no latter than 2:15pm.
AT&T Host: Dahlia Mallkhi.


2:30 - 3:30 p.m
Friday, December 13, 1996

The discrete logarithm problem plays a central role in cryptography, and understanding the computational complexity of this and related problems is essential to understanding the security of many cryptosystems. This research considers the computational complexity of the discrete logarithm and related problems in the context of ``generic algorithms''---that is, algorithms which do not exploit any special properties of the encodings of group elements, other than the property that each group element is encoded as a unique binary string. Lower bounds on the complexity of these problems are proved that match the known upper bounds. Also, a new method for correcting a faulty Diffie-Hellman oracle is presented.

Document last modified on December 6, 1996