After Diffie and Hellman proposed a public key cryptosystem firstly, some kinds of public key cryptosystems are proposed, and DSA, ElGamal cryptosystems are based on the difficulty of the discrete logarithm problem. In these systems, modular exponentiation operation to compute $g^x$ p is the most important but the most expensive operation, and so these systems are not suitable for small devices such as smart cards which have weak computability.
One of solutions to get efficient performance is to use precomutation, and this has two ways. The first way is to refer table elements during computation for given x, but still this requires too large memory and too many operations. The second way is to generate randomly distributed pairs of the form (x, $g^x$ p) using combination of table elements.
In this paper, we propose a secure and efficient method to generate (x, $g^x$ p) with small table in which table elements are updated periodically. To update table elements, we use a concept of SASC. We prove that proposed method is secure by showing that generated value x has a randomness property and that server can not know any information from received data. And we show this is secure against both passive attacks and active attacks, especially secure against attacks using orthogonal lattice reduction.
By using proposed method, one can get high performance improvement. For example, in DSA using a 160bit exponent it requires only 27 modular multiplication operations and small memory to store 20 pairs of 512bit numbers. In this case, it uses only 32% of operations and 58% of memory compared with previous method.
