Abstract
We show that the elliptic curve analogue of the linear congruential generator produces sequences with high linear complexity and good multidimensional distribution.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P. Beelen J. Doumen (2002) Pseudorandom sequences from elliptic curves. Finite Fields with Applications to Coding Theory, Cryptography and Related Areas\/, Springer-Verlag Berlin 37–52
I. Blake G. Seroussi N. Smart (1999) Elliptic Curves in Cryptography, London Math. Soc., Lecture Note Series Cambridge University Press Cambridge
T. W. Cusic C. Ding A. Renvall (1998) Stream Ciphers and Number Theory Elsevier Amsterdam
E. El Mahassni and I. E. Shparlinski, On the uniformity of distribution of congruential generators over elliptic curves, In Proc. Intern. Conf. on Sequences and Their Applications, Bergen 2001, Springer-Verlag, London, (2002) pp. 257--264.
A. M. Frieze J. Håstad R. Kannan J. C. Lagarias A. Shamir (1988) ArticleTitleReconstructing truncated integer variables satisfying linear congruence SIAM J. Comp. 17 262–280 Occurrence Handle0654.10006
G. Gong T. A. Berson D. A. Stinson (2000) Elliptic curve pseudorandom sequence generators, Lecture Notes in Computer Science Springer-Verlag Berlin 34–49
G. Gong and C. C. Y. Lam, Linear recursive sequences over elliptic curves, Proc. Intern. Conf. on Sequences and Their Applications, Bergen 2001, Springer-Verlag, London, (2002) pp. 182–196.
S. Hallgren, Linear congruential generators over elliptic curves, Preprint CS-94-143\/, Dept. of Comp. Sci., Cornegie Mellon Univ., (1994) pp. 1–10.
A. Joux J. Stern (1998) ArticleTitleLattice reduction: A toolbox for the cryptanalyst J. Cryptology 11 161–185 Occurrence Handle0919.94011 Occurrence Handle1633944
H. Krawczyk (1992) ArticleTitleHow to predict congruential generators J. Algorithms 13 527–545 Occurrence Handle0784.65006 Occurrence Handle1187200
S. V. Konyagin I. Shparlinski (1999) Character Sums with Exponential Functions and Their Applications Cambridge University Press Cambridge Occurrence Handle0933.11001
D. R. Kohel I. E. Shparlinski (2000) Exponential sums and group generators for elliptic curves over finite fields, Lecture Notes in Computer Science Springer-Verlag Berlin 395–404
J. C. Lagarias, Pseudorandom number generators in cryptography and number theory, In Proc. Symp. in Appl. Math., Amer. Math. Soc., Providence, RI, Vol. 42 (1990) pp. 115--143.
C. C. Y. Lam and G. Gong, Randomness of elliptic curve sequences, Research Report CORR 2002-18, Faculty of Math., Univ. Waterloo, Waterloo, (2002) pp. 1–11.
A. J. Menezes P. C. Oorschot Particlevan S. A. Vanstone (1996) Handbook of Applied Cryptography CRC Press Boca Raton, FL
H. Niederreiter (1978) ArticleTitleQuasi-Monte Carlo methods and pseudo-random numbers Bull. Amer. Math. Soc. 84 957–1041 Occurrence Handle0404.65003 Occurrence Handle10.1090/S0002-9904-1978-14532-7 Occurrence Handle508447
H. Niederreiter (1992) Random Number Generation and Quasi–Monte Carlo Methods SIAM Philadelphia Occurrence Handle0761.65002
H. Niederreiter M. Vielhaber (1997) ArticleTitleLinear complexity profiles: Hausdorff dimensions for almost perfect profiles and measures for general profiles J. Compl. 13 353–383 Occurrence Handle0934.94013 Occurrence Handle1475570
R. A. Rueppel (1986) Analysis and Design of Stream Ciphers Springer-Verlag Berlin Occurrence Handle0618.94001
I. E. Shparlinski (2000) ArticleTitleOn the Naor–Reingold pseudo-random number function from elliptic curves Appl. Algebra Eng., Commun. Comput. 11 27–34 Occurrence Handle1011.11055 Occurrence Handle1817696
I. E. Shparlinski J. H. Silverman (2001) ArticleTitleOn the linear complexity of the Naor–Reingold pseudo-random function from elliptic curves Designs, Codes and Cryprography 24 279–289 Occurrence Handle1077.11504 Occurrence Handle1857142
J. H. Silverman (1995) The Arithmetic of Elliptic Curves Springer-Verlag Berlin
S. G. Vlăduţ (1999) ArticleTitleCyclicity statistics for elliptic curves over finite fields Finite Fields Their Appl. 5 13–25 Occurrence Handle0927.11032
S. G. Vlăduţ (1999) ArticleTitle A note on the cyclicity of elliptic curves over finite field extensions Finite Fields Their Appl. 5 354–363 Occurrence Handle1022.11030
Author information
Authors and Affiliations
Corresponding author
Additional information
communicated by: A. Menezes
AMS Classification: 11T23, 14H52, 65C10
Rights and permissions
About this article
Cite this article
Hess, F., Shparlinski, I.E. On the Linear Complexity and Multidimensional Distribution of Congruential Generators over Elliptic Curves. Des Codes Crypt 35, 111–117 (2005). https://doi.org/10.1007/s10623-003-6153-0
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10623-003-6153-0