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 language | English |
---|---|
Title of host publication | CRYPTOGRAPHY AND COMPUTATIONAL NUMBER THEORY |
Editors | K. Y. Lam, Igor Shparlinski, H. Wang, C. P. Xing |
Place of Publication | Basel |
Publisher | BIRKHAUSER VERLAG AG |
Pages | 331-342 |
Number of pages | 12 |
ISBN (Print) | 3-7643-6510-2 |
DOIs | |
Publication status | Published - 2001 |
Event | Workshop on Cryptography and Computational Number Theory (CCNT 99) - Singapore, Singapore Duration: 22 Nov 1999 → 26 Nov 1999 |
Publication series
Name | PROGRESS IN COMPUTER SCIENCE AND APPLIED LOGIC |
---|---|
Publisher | BIRKHAUSER VERLAG AG |
Volume | 20 |
Conference
Conference | Workshop on Cryptography and Computational Number Theory (CCNT 99) |
---|---|
Country/Territory | Singapore |
City | Singapore |
Period | 22/11/99 → 26/11/99 |
Keywords
- SCHEMES