Abstract
Most of the work done in cryptography in the last few years depend on the hardness of a few specific number theoretic problems, such as factoring, discrete log, etc. Since no one has so far been able to prove that these problems are genuinely hard, it is clearly of interest to find new candidates for hard problems. In this paper, we propose such a new candidate problem. namely the problem of predicting a sequence of consecutive Legendre (Jacobi) symbols modulo a prime (composite), when the starting point and possibly also the prime is unknown. Clearly, if this problem turns out to be hard, it can be used directly to construct a cryptographically strong pseudorandom bitgenerator. Its complexity seems to be unrelated to any of the well known number theoretical problems, whence it may be able to survive the discovery of fast factoring or discrete log algorithms. Although the randomness of Legendre sequences has part of the folklore in number theory at least since the thirties, they have apparently not been considered for use in cryptography before.
This research was supported by the Danish Natural Science Research Council.
Chapter PDF
Similar content being viewed by others
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
Bach: “Realistic Analysis of Some Randomized Algorithms”, Proc. of STOC 87.
Blum and Micali: How to Generate Cryptographically Strong Sequences of Pseudorandom Bits”, SIAM J. of Comp., vol.13, 1984, pp.850–864.
Boppana and Hirschfeld: “Pseudorandom Generators and Complexity Classes”, Manuscript, MIT, 1987.
Burde: “Verteilungseigenschaften von Potenzresten”, J. Reine Angev. Math 249, pp.133–172, 1971.
Burgess: “The Distribution of Quadratic Residues and non-Residues”, Mathematica 4 (1957), pp.106–112.
Davenport: “On the Distribution of Quadratic Residues (mod p)”, J. London Math. Soc., 8 (1933), pp.46–52.
Elliott: “A Restricted mean value Theorem”, J. London Math. Soc. (2), 1 (1969), pp.447–460.
Kranakis: “Primality and Cryptography”, Wiley-Teubner Series in Computer Science, 1986.
Micali and Schorr: “Super-Efficient, Perfect Random Number Generators”, these proceedings.
Perron: “Bemerkungen uber die Verteilung der quadratischen Reste”, Math. Z. 56 (1952), pp. 122–130.
Rueppel: “Linear Complexity and Random Sequences”, Proc. of EuroCrypt 85, pp.167–191, Springer.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Damgård, I.B. (1990). On The Randomness of Legendre and Jacobi Sequences. In: Goldwasser, S. (eds) Advances in Cryptology — CRYPTO’ 88. CRYPTO 1988. Lecture Notes in Computer Science, vol 403. Springer, New York, NY. https://doi.org/10.1007/0-387-34799-2_13
Download citation
DOI: https://doi.org/10.1007/0-387-34799-2_13
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-0-387-97196-4
Online ISBN: 978-0-387-34799-8
eBook Packages: Springer Book Archive