Speeding up Discrete Log and Factoring Based Schemes via Precomputations

We present fast and practical methods for generating randomly
distributed pairs of the form (x, g~ mod p) or (x, x ~ rood N), using
precomputation. These generation schemes are of wide applicability
for speeding-up public key systems that depend on exponentiation and
offer a smooth memory-speed trade-off. The steps involving exponentiation
in these systems can be reduced significantly in many cases. Our
schemes are most suited for server applications. We present security analyses
of our schemes using standard assumptions, including analyses for
fully adaptive attacks. Our methods are novel in the sense that they
identify and thoroughly exploit the randomness issues related to the instances
generated in these public-key schemes. Our constructions use
random walks on Cayley (expander) graphs over Abelian groups. Our
analysis involves non-linear versions of lattice problems. It appears that
any realistic attack on our schemes would need to solve such problems.