Distribution of modular sums and the security of the server aided exponentiation

Phong Q. Nguyen, Igor Shparlinski, Jacques Stern

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

Abstract

We obtain some uniformity of distribution results for the values of modular sums of the form

Sigma (n)(j=1) a(j)x(j) (mod M) (x(1),... , x(n)) epsilonB

where M greater than or equal to 1 is an integer, a(1),..., a(n) are elements of the residue ring module M, selected unformly at random, and a is an arbitrary set of n-dimensional integer vectors. In some partial cases, for very special sets a, 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).

Original languageEnglish
Title of host publicationCRYPTOGRAPHY AND COMPUTATIONAL NUMBER THEORY
EditorsK. Y. Lam, Igor Shparlinski, H. Wang, C. P. Xing
Place of PublicationBasel
PublisherBIRKHAUSER VERLAG AG
Pages331-342
Number of pages12
ISBN (Print)3-7643-6510-2
DOIs
Publication statusPublished - 2001
EventWorkshop on Cryptography and Computational Number Theory (CCNT 99) - Singapore, Singapore
Duration: 22 Nov 199926 Nov 1999

Publication series

NamePROGRESS IN COMPUTER SCIENCE AND APPLIED LOGIC
PublisherBIRKHAUSER VERLAG AG
Volume20

Conference

ConferenceWorkshop on Cryptography and Computational Number Theory (CCNT 99)
CountrySingapore
CitySingapore
Period22/11/9926/11/99

Keywords

  • SCHEMES

Cite this