# DIMACS Special Year on Networks Seminar

## Title:

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

## Speaker:

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

Document last modified on November 13, 1996