Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

True Random Number Generators Secure in a Changing Environment

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 2779))

  • 3853Accesses

  • 87Citations

Abstract

A true random number generator (TRNG) usually consists of two components: an “unpredictable” source with high entropy, and arandomness extractor — a function which, when applied to the source, produces a result that is statistically close to the uniform distribution. When the output of a TRNG is used for cryptographic needs, it is prudent to assume that an adversary may have some (limited) influence on the distribution of the high-entropy source. In this work:

  1. 1

    We define a mathematical model for the adversary’s influence on the source.

  2. 2

    We show a simple and efficient randomness extractor andprove that it works forall sources of sufficiently high-entropy, even if individual bits in the source are correlated.

  3. 3

    Security is guaranteed even if an adversary has (bounded) influence on the source.

Our approach is based on a related notion of “randomness extraction” which emerged in complexity theory. We stress that the statistical randomness of our extractor’s output isproven, and is not based on any unproven assumptions, such as the security of cryptographic hash functions.

A sample implementation of our extractor and additional details can be found at a dedicated web page [Web].

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

  1. Bellare, M., Rompel, J.: Randomness-efficient oblivious sampling. In: 35th Annual Symposium on Foundations of Computer Science (1994)

    Google Scholar 

  2. Carter, L., Wegman, M.: Universal hash functions. JCSS: Journal of Computer and System Sciences 18, 143–154 (1979)

    Article MathSciNet MATH  Google Scholar 

  3. Eastlake III, D., Crocker, S., Schiller, J.: Randomness recommendations for security, RFC 1750 (December 1994)

    Google Scholar 

  4. Gladman, B.: A specification for Rijndael, the AES algorithm (2002), Available fromhttp://fp.gladman.plus.com/cryptography_technology/rijndael/aesspec.pdf

  5. Goldberg, I., Wagner, D.: Randomness and the netscape browser. Dr. Dobb’s Journal, 66–70 (1996)

    Google Scholar 

  6. Impagliazzo, R., Levin, L.A., Luby, M.: Pseudorandom generation from one-way functions. In: Proceedings of the 21st ACM Symposium on Theory of Computing (1989)

    Google Scholar 

  7. Jun, B., Kocher, P.: The Intel random number generator. Technical report, Cryptography Research Inc. (1999), Available fromhttp://www.intel.com/design/security/rng/rngppr.htm

  8. Marsaglia, G.: DIEHARD, a battery of tests for random number generators (1995), Available fromhttp://stat.fsu.edu/~geo/diehard.html

  9. Nisan, N., Ta-Shma, A.: Extracting randomness: A survey and new constructions. JCSS: Journal of Computer and System Sciences 58 (1999)

    Google Scholar 

  10. Nisan, N., Zuckerman, D.: Randomness is linear in space. Journal of Computer and System Sciences 52(1), 43–52 (1996)

    Article MathSciNet MATH  Google Scholar 

  11. Peres, Y.: Iterating von Neumann’s procedure for extracting random bits. Ann. Statist. 20(1), 590–597 (1992)

    Article MathSciNet MATH  Google Scholar 

  12. Shaltiel, R.: Recent developments in extractors. Bulletin of the European Association for Theoretical Computer Science 77 (2002)

    Google Scholar 

  13. Trevisan, L., Vadhan, L.: Pseudorandomness and average-case complexity via uniform reductions. In: Proceedings of the 17th Annual Conference on Computational Complexity (2002)

    Google Scholar 

  14. von Neumann, J.: Various techniques used in connection with random digits. Applied Math. Series 12, 36–38 (1951)

    Google Scholar 

  15. Wegman, M.N., Carter, J.L.: New hash functions and their use in authentication and set equality. JCSS: Journal of Computer and System Sciences 22 (1981)

    Google Scholar 

  16. Web page for this paper, Available fromhttp://www.wisdom.weizmann.ac.il/~tromer/trng/

  17. Zimmermann, P.R.: PGP: Source Code and Internals. MIT Press, Cambridge (1995)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and, Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel

    Boaz Barak, Ronen Shaltiel & Eran Tromer

Authors
  1. Boaz Barak
  2. Ronen Shaltiel
  3. Eran Tromer

Editor information

Editors and Affiliations

  1. Comodo Research Lab, BD7 1DQ, Bradford, UK

    Colin D. Walter

  2. Information Security Research Center, Istanbul Commerce University, 34112, Eminönü, Istanbul, Turkey

    Çetin K. Koç

  3. Horst Görtz Institute for IT Security, Ruhr University Bochum, 44780, Bochum, Germany

    Christof Paar

Rights and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Barak, B., Shaltiel, R., Tromer, E. (2003). True Random Number Generators Secure in a Changing Environment. In: Walter, C.D., Koç, Ç.K., Paar, C. (eds) Cryptographic Hardware and Embedded Systems - CHES 2003. CHES 2003. Lecture Notes in Computer Science, vol 2779. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45238-6_14

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp