DIMACS Special Year on Networks Seminar


How to speed up discrete log public-key systems via pre-computation


R. Venkatesan


CoRE Building, Computer Science, 3rd Floor Conference Room 301A
Rutgers University


2:30 - 3:30 p.m
Friday, November 15, 1996

We present very fast and practical methods for generating randomly distributed pairs of the form $(x,g^x \bmod p)$ or $(x,x^e \bmod n)$ using pre-computation. These generation schemes can be used in various public-key schemes with a smooth memory-speed tradeoff and the cost of exponentiating is reduced to approximately 16 modular multiplications. We show, modulo some hardness assumptions, that we {\em preserve} the security in the sense that if a public-key scheme is broken when one uses our generation scheme, then one can break the original scheme. A scheme for speed-up that does not admit such analysis may introduce insecurity and actually get broken later (e.g. \cite{schnorr91,dr-break-schnorr93}).

Document last modified on November 13, 1996