Abstract
We obtain some uniformity of distribution results for the values of modular sums of the form
where M ≥ 1 is an integer, a1,…, an are elements of the residue ring modulo M, selected unformly at random, and β is an arbitrary set of n-dimensional integer vectors. In some partial cases, for very special sets β, some results of this kind have been known, however our estimates are more precise and more general. Our technique is based on fairly simple properties of exponential sums. We also give cryptographic applications of some of these results. In particular, we consider an extension of a pseudo-random number generator due to V. Boyko, M. Peinado and R Venkatesan, and establish the security of some discrete logarithm based signature schemes making use of this generator (in both its original and extended forms). One of these schemes, which uses precomputation is well known. The other scheme which uses server aided computation, seems to be new. We show that for a certain choice of parameters one can guarantee an essential speed-up of both of these schemes without compromising the security (compared to the traditional discrete logarithm based signature scheme).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Ajtai, Generating hard instances of lattice problems, Electronic Colloq. on Comp. Compl., Univ. of Trier, TR96–007 (1996), 1–29.
V. Boyko, M. Peinado and R. Venkatesan, Speeding up discrete log and factoring based schemes via precomputations, Proc. of Eurocrypt’98, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1403 (1998), 221–234.
E. Brickell, D.M. Gordon, K.S. McCurley, and D. Wilson, Fast exponentiation with precomputation,Proc. of Eurocrypt’92, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 658 (1993), 200–207.
E. F. Brickell and K. S. McCurley, An interactive identification scheme based on discrete logarithms and factoring, Journal of Cryptology, 5 (1992), 29–39.
T. El Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms,IEEE Trans. Inform. Theory, 31 (1985), 469–472.
O. Goldreich, Modern Cryptography, Probabilistic Proofs and Pseudorandomness, Springer-Verlag, Berlin, 1999.
D.M. Gordon, A survey of fast exponentiation methods, Journal of Algorithms, 27 (1998), 129–146.
F. Griffin and I. E. Shparlinski, On the linear complexity of the Naor-Reingold pseudo-random function, Proc. of 2nd Intern. Conf. on Inform. and Commun. Security, Sydney, 1999, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1999,301–308.
R. Impagliazzo and M. Naor, Efficient cryptographic schemes provably as secure as subset sum, J. Cryptology, 9 (1996), 199--216.
C. H. Lim and P. J. Lee, More flexible exponentiation with precomputation,Proc. of Crypto’94, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 839 (1994), 95–107.
M. Luby, Pseudorandomness and cryptographic applications, Princeton University Press, 19969.
J. Merkle and R. Werchner, On the security of server-aided RSA protocols, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1431 (1998), 99–116.
M. Naor and O. Reingold, Synthesizers and their application to the parallel construction of pseudo-random functions, J. Comp. and Sys. Sci., 58 (1999), 336–375.
National Institute of Standards and Technology (NIST), FIPS Publication 186: Digital Signature Standard, May 1994.
P. Nguyen and J. Stern, The hardness of the hidden subset sum problem and its cryptographic implications,Proc. of Crypto’99, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1666 (1999), 31–46.
P. de Rooij, On the security of the Schnorr scheme using preprocessing, Proc. of Eurocrypt’91, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 547 (1991), 71–80.
P. de Rooij, Efficient exponentiation using precomputation and vector addition chains, Proc. of Eurocrypt’94, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 950 (1995), 389–399.
P. de Rooij, On Schnorr’s preprocessing for digital signature schemes, Journal of Cryptology, 10 (1997), 1–16.
C. P. Schnorr, Efficient identification and signatures for smart cards, Proc. of Crypto’89, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 435 (1990), 239–252.
C. P. Schnorr, Efficient signature generation by smart cards, Journal of Cryptology, 4 (1991), 161–174.
I. M. Vinogradov, Elements of number theory, Dover Publ., New York, 1954.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer Basel AG
About this paper
Cite this paper
Nguyen, P.Q., Shparlinski, I.E., Stern, J. (2001). Distribution of Modular Sums and the Security of the Server Aided Exponentiation. In: Lam, KY., Shparlinski, I., Wang, H., Xing, C. (eds) Cryptography and Computational Number Theory. Progress in Computer Science and Applied Logic, vol 20. Birkhäuser, Basel. https://doi.org/10.1007/978-3-0348-8295-8_24
Download citation
DOI: https://doi.org/10.1007/978-3-0348-8295-8_24
Publisher Name: Birkhäuser, Basel
Print ISBN: 978-3-0348-9507-1
Online ISBN: 978-3-0348-8295-8
eBook Packages: Springer Book Archive