# DIMACS Special Year on Networks Seminar

## Title:

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

R. Venkatesan
Bellcore

## Place:

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

## Time:

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

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}).