Abstract
We present fast and practical methods for generating randomly distributed pairs of the form (x,gx mod p) or (x, xe mod N), using precomputation. These generation schemes axe 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.
Part of the work done while at Bellcore.
Part of the work was done while visiting ICSI, Berkeley, CA.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
W. Aiello, S. Rajagopalan, and R. Venkatesan. Design of practical and provably good random number generators. In Proceedings of the 6th Annual Symposium on Discrete Algorithms, pages 1–9, San Francisco, January 1995. ACM Press. (also to appear in Journal of Algorithms).
N. Alon and Y. Roichman. Random Cayley graphs and expanders. Random Structures and Algorithms, 5, 1994.
D. Boneh and R. Venkatesan. Breaking RSA may not be equivalent to factoring. Eurocrypt '98, this proceedings.
E. Brickell. Solving low density knapsacks. In Proceedings of Crypto'83, pages 25–37, New York, 1984. Plenum Press.
E. F. Brickell, D. M. Gordon, K. S. McCurley, and D. B. Wilson. Fast exponentiation with precomputation. In R. A. Rueppel, editor, Advances in Cryptology: EUROCRYPT '92, volume 658 of Lecture Notes in Computer Science, pages 200–207, Berlin, 1993. Springer-Verlag.
R. Canetti. Towards realizing random oracles: Hash functions that hide all partial information. In Advances in Cryptology — Crypto'97, Lecture Notes in Computer Science, 1997.
D. Coppersmith. Small solutions to polynomial equations and low exponent RSA vulnerabilities. Journal of Cryptology, 10(4), 1997.
M. J. Coster, A. Joux, B. A. LaMacchia, A. M. Odlyzko, C. P. Schnorr, and J. Stern. Improved low-density subset sum algorithms. In Computational Complexity 2, pages 111–128. Birkhäuser-Verlag, Basel, 1992.
P. J. N. de Rooij. On the security of the Schnorr scheme using preprocessing. In D. W. Davies, editor, Advances in Cryptology: EUROCRYPT '91, volume 547 of Lecture Notes in Computer Science, pages 71–80, Berlin, 1991. Springer-Verlag.
P. J. N. de Rooij. Efficient exponentiation using precomputation and vector addition chains. In A. De Santis, editor, Advances in Cryptology: EUROCRYPT '94, volume 950 of Lecture Notes in Computer Science, pages 389–399, Berlin, 1994. Springer-Verlag.
P. J. N. de Rooij. On Schnorr's preprocessing for digital signature schemes. Journal of Cryptology, 10(1):1–16, 1997.
W. Diffie and M. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22:644–654, 1976.
Digital Signature Standard. National Bureau of Standards FIPS Publication 186, 1994.
T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inform. Theory, 31:469–472, 1985.
J. Fischer and J. Stern. An efficient pseudo-random generator provably as secure as syndrome decoding. In U. Maurer, editor, Advances in Cryptology: EUROCRYPT '96, volume 1070 of Lecture Notes in Computer Science, pages 245–255, Berlin, 1996. Springer-Verlag.
R. Impagliazzo and M. Naor. Efficient cryptographic schemes provably as secure as subset sum. Journal of Cryptology, 9(4):199–216, 1996.
J. Lagarias and A. Odlyzko. Solving low density subset sum problems. Journal of the ACM, 32, 1985.
A. Lenstra, H. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261:513–548, 1982.
C. H. Lim and P. J. Lee. More flexible exponentiation with precomputation. In Advances in Cryptology — Crypto'94, Lecture Notes in Computer Science, 1994.
R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
V. I. Nechaev. Complexity of determinate algorithm for the discrete logarithm. Mathematical Notes, 55(2):165–172, 1994.
D. Pointcheval and J. Stern. Security proofs for signature schemes. In U. Maurer, editor, Advances in Cryptology — Eurocrypt'96, Lecture Notes in Computer Science, 1996.
C. P. Schnorr. Efficient identification and signatures for smart cards. In G. Brassard, editor, Advances in Cryptology: CRYPTO '89, volume 435 of Lecture Notes in Computer Science, pages 239–252, Berlin, 1990. Springer-Verlag.
C. P. Schnorr. Efficient signature generation by smart cards. J. Cryptology, 4:161–174, 1991.
C. P. Schnorr and M. Euchner. Lattice basis reduction: Improved practical algorithms for solving subset sum problems. Mathematical Programming, 66:181–199, 1994.
C. P. Schnorr and H. Hörner. Attacking the Chor-Rivest cryptosystem by improved lattice reduction. In L. Guillou and J. Quisquater, editors, Advances in Cryptology — Eurocrypt'95, Lecture Notes in Computer Science, 1995.
V. Shoup. On the security of a practical identification scheme. In Ueli Maurer, editor, Advances in Cryptology: EUROCRYPT '96, volume 1070 of Lecture Notes in Computer Science, pages 344–353, Berlin, 1996. Springer-Verlag.
V. Shoup. Lower bounds on discrete logarithms and related problems. In Advances in Cryptology — Eurocrypt'97, Lecture Notes in Computer Science, 1997.
M. J. Wiener. Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory, 36(3):553–558, 1990.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boyko, V., Peinado, M., Venkatesan, R. (1998). Speeding up discrete log and factoring based schemes via precomputations. In: Nyberg, K. (eds) Advances in Cryptology — EUROCRYPT'98. EUROCRYPT 1998. Lecture Notes in Computer Science, vol 1403. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054129
Download citation
DOI: https://doi.org/10.1007/BFb0054129
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64518-4
Online ISBN: 978-3-540-69795-4
eBook Packages: Springer Book Archive