Abstract

A binary sequence was constructed from 1.7×107 polarization measurements of single photons from a spontaneous parametric downconversion source, under pumping conditions similar to those used in optical quantum cryptography. To search for correlations in the polarization measurement outcomes, we subjected the sequence to a suite of tests developed at the National Institute of Standards and Technology (NIST) for the assessment of algorithmic random-number generators. The bias of the sequence was low enough to allow all fifteen tests to be applied directly to the polarization outcomes without using any numerical unbiasing procedures. No statistically significant deviations from randomness were observed, other than those related to this small uncorrected bias.

© 2010 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. S. Scheel, “Single-photon sources—an introduction,” J. Mod. Opt. 56, 141–160 (2009).
    [CrossRef]
  2. L. Mandel, “Quantum effects in one-photon and two-photon interference,” Rev. Mod. Phys. 71, S274–S282 (1999).
    [CrossRef]
  3. A. Zeilinger, “Experiment and the foundations of quantum physics,” Rev. Mod. Phys. 71, S288–S297 (1999).
    [CrossRef]
  4. N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, “Quantum cryptography,” Rev. Mod. Phys. 74, 145–195 (2002).
    [CrossRef]
  5. V. Scarani, H. Bechmann-Pasquinucci, N. Cerf, M. Dusek, N. Lütkenhaus, and M. Peev, “The security of practical quantum key distribution,” Rev. Mod. Phys. 81, 1301–1350 (2009).
    [CrossRef]
  6. A. Steane, “Quantum computing,” Rep. Prog. Phys. 61, 117–173 (1998).
    [CrossRef]
  7. A. Galindo and M. A. Martín-Delgado, “Information and computation: classical and quantum aspects,” Rev. Mod. Phys. 74, 347–423 (2002).
    [CrossRef]
  8. T. Erber, “Testing the randomness of quantum mechanics: nature’s ultimate cryptogram?” Ann. N.Y. Acad. Sci. 755, 748–756 (1995).
    [CrossRef]
  9. M. P. Silverman, W. Strange, C. R. Silverman, and T. C. Lipscombe, “Tests of alpha-, beta-, and electron capture decays for randomness,” Phys. Lett. A 262, 265–273 (1999).
    [CrossRef]
  10. M. P. Silverman and W. Strange, “Experimental tests for randomness of quantum decay examined as a Markov process,” Phys. Lett. A 272, 1–9 (2000).
    [CrossRef]
  11. M. P. Silverman, W. Strange, C. R. Silverman, and T. C. Lipscombe, “Tests for randomness of spontaneous quantum decay,” Phys. Rev. A 61, 042106 (2000).
    [CrossRef]
  12. A. Stefanov, N. Gisin, O. Guinnard, L. Guinnard, and H. Zbinden, “Optical quantum random number generator,” J. Mod. Opt. 47, 595–598 (2000).
  13. H.-Q. Ma, Y. Xie, and L.-A. Wu, “Random number generation based on the time of arrival of single photons,” Appl. Opt. 44, 7760–7763 (2005).
    [CrossRef] [PubMed]
  14. M. Stipcevid and B. Medved Rogina, “Quantum random number generator based on photonic emission in semiconductors,” Rev. Sci. Instrum. 78, 045104 (2007).
    [CrossRef]
  15. J. F. Dynes, Z. L. Yuan, A. W. Sharpe, and A. J. Shields, “A high speed, postprocessing free, quantum random number generator,” Appl. Phys. Lett. 93, 031109 (2008).
    [CrossRef]
  16. H.-Q. Ma, S.-M. Wang, D. Zhang, J.-T. Chang, L.-L. Ji, Y.-X. Hou, and L.-A. Wu, “A Random number generator based on quantum entangled photon pairs,” Chin. Phys. Lett. 21, 1961–1964 (2004).
    [CrossRef]
  17. T. Jennewein, U. Achleitner, G. Weihs, H. Weinfurter, and A. Zeilinger, “A fast and compact random number generator,” Rev. Sci. Instrum. 71, 1675–1680 (2000).
    [CrossRef]
  18. A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, and S. Vo, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (revised),” Natl. Inst. Stand. Technol. (U. S.) Spec. Publ. 800-22rev1 (2008) http://csrc. nist. gov/groups/ST/toolkit/rng/documentation_software. html.
  19. D. C. Burnham and D. L. Weinberg, “Observation of simutaneity in parametric production of optical photon pairs,” Phys. Rev. Lett. 25, 84–87 (1970).
    [CrossRef]
  20. L. Mandel and E. Wolf, Optical Coherence and Quantum Optics (Cambridge Univ. Press, 1995).
  21. C. K. Hong and L. Mandel, “Experimental realization of a localized one-photon state,” Phys. Rev. Lett. 56, 58–60 (1986).
    [CrossRef] [PubMed]
  22. D. Branning, S. Bhandari, and M. Beck, “Low-cost coincidence-counting electronics for undergraduate quantum optics,” Am. J. Phys. 77, 667–670 (2009).
    [CrossRef]
  23. There is an error in the current NIST publication concerning this test: in section , although all of the formulae appear to be correct, the last three tables of probabilities (for M=512, 1000, and 10000) are not. The source code for the Statistical Test Suite provided by NIST, to the extent that it makes use of these incorrect probabilities, is also in error.
  24. S.-J. Kim, K. Umeno, and A. Hasegawa, On the NIST Statistical Test Suite for RandomnessIEICE Tech. Rep. (IEICE, 2003) Vol. 103, 21–27.
  25. S.-J. Kim, K. Umeno, and A. Hasegawa, Corrections of the NIST Statistical Test Suite for Randomness Report 2004/018 (Cryptology ePrint Archive, 2004).
  26. The current NIST publication also contains an error regarding this test: on page 2–32, Eq. , the absolute value of Sk should be divided by n.
  27. J. Von Neumann, “Various techniques used in connection with random digits,” Nat. Bur. Stand. (U. S.) Appl. Math Series No. 12 (GPO, 1951) pp. 36–38.
  28. Y. Peres, “Iterating Von Neumann’s procedure for extracting random bits,” Ann. Stat. 20, 590–597 (1992).
    [CrossRef]

2009 (3)

S. Scheel, “Single-photon sources—an introduction,” J. Mod. Opt. 56, 141–160 (2009).
[CrossRef]

V. Scarani, H. Bechmann-Pasquinucci, N. Cerf, M. Dusek, N. Lütkenhaus, and M. Peev, “The security of practical quantum key distribution,” Rev. Mod. Phys. 81, 1301–1350 (2009).
[CrossRef]

D. Branning, S. Bhandari, and M. Beck, “Low-cost coincidence-counting electronics for undergraduate quantum optics,” Am. J. Phys. 77, 667–670 (2009).
[CrossRef]

2008 (1)

J. F. Dynes, Z. L. Yuan, A. W. Sharpe, and A. J. Shields, “A high speed, postprocessing free, quantum random number generator,” Appl. Phys. Lett. 93, 031109 (2008).
[CrossRef]

2007 (1)

M. Stipcevid and B. Medved Rogina, “Quantum random number generator based on photonic emission in semiconductors,” Rev. Sci. Instrum. 78, 045104 (2007).
[CrossRef]

2005 (1)

2004 (1)

H.-Q. Ma, S.-M. Wang, D. Zhang, J.-T. Chang, L.-L. Ji, Y.-X. Hou, and L.-A. Wu, “A Random number generator based on quantum entangled photon pairs,” Chin. Phys. Lett. 21, 1961–1964 (2004).
[CrossRef]

2002 (2)

A. Galindo and M. A. Martín-Delgado, “Information and computation: classical and quantum aspects,” Rev. Mod. Phys. 74, 347–423 (2002).
[CrossRef]

N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, “Quantum cryptography,” Rev. Mod. Phys. 74, 145–195 (2002).
[CrossRef]

2000 (4)

T. Jennewein, U. Achleitner, G. Weihs, H. Weinfurter, and A. Zeilinger, “A fast and compact random number generator,” Rev. Sci. Instrum. 71, 1675–1680 (2000).
[CrossRef]

M. P. Silverman and W. Strange, “Experimental tests for randomness of quantum decay examined as a Markov process,” Phys. Lett. A 272, 1–9 (2000).
[CrossRef]

M. P. Silverman, W. Strange, C. R. Silverman, and T. C. Lipscombe, “Tests for randomness of spontaneous quantum decay,” Phys. Rev. A 61, 042106 (2000).
[CrossRef]

A. Stefanov, N. Gisin, O. Guinnard, L. Guinnard, and H. Zbinden, “Optical quantum random number generator,” J. Mod. Opt. 47, 595–598 (2000).

1999 (3)

M. P. Silverman, W. Strange, C. R. Silverman, and T. C. Lipscombe, “Tests of alpha-, beta-, and electron capture decays for randomness,” Phys. Lett. A 262, 265–273 (1999).
[CrossRef]

L. Mandel, “Quantum effects in one-photon and two-photon interference,” Rev. Mod. Phys. 71, S274–S282 (1999).
[CrossRef]

A. Zeilinger, “Experiment and the foundations of quantum physics,” Rev. Mod. Phys. 71, S288–S297 (1999).
[CrossRef]

1998 (1)

A. Steane, “Quantum computing,” Rep. Prog. Phys. 61, 117–173 (1998).
[CrossRef]

1995 (1)

T. Erber, “Testing the randomness of quantum mechanics: nature’s ultimate cryptogram?” Ann. N.Y. Acad. Sci. 755, 748–756 (1995).
[CrossRef]

1992 (1)

Y. Peres, “Iterating Von Neumann’s procedure for extracting random bits,” Ann. Stat. 20, 590–597 (1992).
[CrossRef]

1986 (1)

C. K. Hong and L. Mandel, “Experimental realization of a localized one-photon state,” Phys. Rev. Lett. 56, 58–60 (1986).
[CrossRef] [PubMed]

1970 (1)

D. C. Burnham and D. L. Weinberg, “Observation of simutaneity in parametric production of optical photon pairs,” Phys. Rev. Lett. 25, 84–87 (1970).
[CrossRef]

Achleitner, U.

T. Jennewein, U. Achleitner, G. Weihs, H. Weinfurter, and A. Zeilinger, “A fast and compact random number generator,” Rev. Sci. Instrum. 71, 1675–1680 (2000).
[CrossRef]

Banks, D.

A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, and S. Vo, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (revised),” Natl. Inst. Stand. Technol. (U. S.) Spec. Publ. 800-22rev1 (2008) http://csrc. nist. gov/groups/ST/toolkit/rng/documentation_software. html.

Barker, E.

A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, and S. Vo, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (revised),” Natl. Inst. Stand. Technol. (U. S.) Spec. Publ. 800-22rev1 (2008) http://csrc. nist. gov/groups/ST/toolkit/rng/documentation_software. html.

Bechmann-Pasquinucci, H.

V. Scarani, H. Bechmann-Pasquinucci, N. Cerf, M. Dusek, N. Lütkenhaus, and M. Peev, “The security of practical quantum key distribution,” Rev. Mod. Phys. 81, 1301–1350 (2009).
[CrossRef]

Beck, M.

D. Branning, S. Bhandari, and M. Beck, “Low-cost coincidence-counting electronics for undergraduate quantum optics,” Am. J. Phys. 77, 667–670 (2009).
[CrossRef]

Bhandari, S.

D. Branning, S. Bhandari, and M. Beck, “Low-cost coincidence-counting electronics for undergraduate quantum optics,” Am. J. Phys. 77, 667–670 (2009).
[CrossRef]

Branning, D.

D. Branning, S. Bhandari, and M. Beck, “Low-cost coincidence-counting electronics for undergraduate quantum optics,” Am. J. Phys. 77, 667–670 (2009).
[CrossRef]

Burnham, D. C.

D. C. Burnham and D. L. Weinberg, “Observation of simutaneity in parametric production of optical photon pairs,” Phys. Rev. Lett. 25, 84–87 (1970).
[CrossRef]

Cerf, N.

V. Scarani, H. Bechmann-Pasquinucci, N. Cerf, M. Dusek, N. Lütkenhaus, and M. Peev, “The security of practical quantum key distribution,” Rev. Mod. Phys. 81, 1301–1350 (2009).
[CrossRef]

Chang, J.-T.

H.-Q. Ma, S.-M. Wang, D. Zhang, J.-T. Chang, L.-L. Ji, Y.-X. Hou, and L.-A. Wu, “A Random number generator based on quantum entangled photon pairs,” Chin. Phys. Lett. 21, 1961–1964 (2004).
[CrossRef]

Dray, J.

A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, and S. Vo, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (revised),” Natl. Inst. Stand. Technol. (U. S.) Spec. Publ. 800-22rev1 (2008) http://csrc. nist. gov/groups/ST/toolkit/rng/documentation_software. html.

Dusek, M.

V. Scarani, H. Bechmann-Pasquinucci, N. Cerf, M. Dusek, N. Lütkenhaus, and M. Peev, “The security of practical quantum key distribution,” Rev. Mod. Phys. 81, 1301–1350 (2009).
[CrossRef]

Dynes, J. F.

J. F. Dynes, Z. L. Yuan, A. W. Sharpe, and A. J. Shields, “A high speed, postprocessing free, quantum random number generator,” Appl. Phys. Lett. 93, 031109 (2008).
[CrossRef]

Erber, T.

T. Erber, “Testing the randomness of quantum mechanics: nature’s ultimate cryptogram?” Ann. N.Y. Acad. Sci. 755, 748–756 (1995).
[CrossRef]

Galindo, A.

A. Galindo and M. A. Martín-Delgado, “Information and computation: classical and quantum aspects,” Rev. Mod. Phys. 74, 347–423 (2002).
[CrossRef]

Gisin, N.

N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, “Quantum cryptography,” Rev. Mod. Phys. 74, 145–195 (2002).
[CrossRef]

A. Stefanov, N. Gisin, O. Guinnard, L. Guinnard, and H. Zbinden, “Optical quantum random number generator,” J. Mod. Opt. 47, 595–598 (2000).

Guinnard, L.

A. Stefanov, N. Gisin, O. Guinnard, L. Guinnard, and H. Zbinden, “Optical quantum random number generator,” J. Mod. Opt. 47, 595–598 (2000).

Guinnard, O.

A. Stefanov, N. Gisin, O. Guinnard, L. Guinnard, and H. Zbinden, “Optical quantum random number generator,” J. Mod. Opt. 47, 595–598 (2000).

Hasegawa, A.

S.-J. Kim, K. Umeno, and A. Hasegawa, Corrections of the NIST Statistical Test Suite for Randomness Report 2004/018 (Cryptology ePrint Archive, 2004).

S.-J. Kim, K. Umeno, and A. Hasegawa, On the NIST Statistical Test Suite for RandomnessIEICE Tech. Rep. (IEICE, 2003) Vol. 103, 21–27.

Heckert, A.

A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, and S. Vo, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (revised),” Natl. Inst. Stand. Technol. (U. S.) Spec. Publ. 800-22rev1 (2008) http://csrc. nist. gov/groups/ST/toolkit/rng/documentation_software. html.

Hong, C. K.

C. K. Hong and L. Mandel, “Experimental realization of a localized one-photon state,” Phys. Rev. Lett. 56, 58–60 (1986).
[CrossRef] [PubMed]

Hou, Y.-X.

H.-Q. Ma, S.-M. Wang, D. Zhang, J.-T. Chang, L.-L. Ji, Y.-X. Hou, and L.-A. Wu, “A Random number generator based on quantum entangled photon pairs,” Chin. Phys. Lett. 21, 1961–1964 (2004).
[CrossRef]

Jennewein, T.

T. Jennewein, U. Achleitner, G. Weihs, H. Weinfurter, and A. Zeilinger, “A fast and compact random number generator,” Rev. Sci. Instrum. 71, 1675–1680 (2000).
[CrossRef]

Ji, L.-L.

H.-Q. Ma, S.-M. Wang, D. Zhang, J.-T. Chang, L.-L. Ji, Y.-X. Hou, and L.-A. Wu, “A Random number generator based on quantum entangled photon pairs,” Chin. Phys. Lett. 21, 1961–1964 (2004).
[CrossRef]

Kim, S.-J.

S.-J. Kim, K. Umeno, and A. Hasegawa, Corrections of the NIST Statistical Test Suite for Randomness Report 2004/018 (Cryptology ePrint Archive, 2004).

S.-J. Kim, K. Umeno, and A. Hasegawa, On the NIST Statistical Test Suite for RandomnessIEICE Tech. Rep. (IEICE, 2003) Vol. 103, 21–27.

Leigh, S.

A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, and S. Vo, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (revised),” Natl. Inst. Stand. Technol. (U. S.) Spec. Publ. 800-22rev1 (2008) http://csrc. nist. gov/groups/ST/toolkit/rng/documentation_software. html.

Levenson, M.

A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, and S. Vo, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (revised),” Natl. Inst. Stand. Technol. (U. S.) Spec. Publ. 800-22rev1 (2008) http://csrc. nist. gov/groups/ST/toolkit/rng/documentation_software. html.

Lipscombe, T. C.

M. P. Silverman, W. Strange, C. R. Silverman, and T. C. Lipscombe, “Tests for randomness of spontaneous quantum decay,” Phys. Rev. A 61, 042106 (2000).
[CrossRef]

M. P. Silverman, W. Strange, C. R. Silverman, and T. C. Lipscombe, “Tests of alpha-, beta-, and electron capture decays for randomness,” Phys. Lett. A 262, 265–273 (1999).
[CrossRef]

Lütkenhaus, N.

V. Scarani, H. Bechmann-Pasquinucci, N. Cerf, M. Dusek, N. Lütkenhaus, and M. Peev, “The security of practical quantum key distribution,” Rev. Mod. Phys. 81, 1301–1350 (2009).
[CrossRef]

Ma, H.-Q.

H.-Q. Ma, Y. Xie, and L.-A. Wu, “Random number generation based on the time of arrival of single photons,” Appl. Opt. 44, 7760–7763 (2005).
[CrossRef] [PubMed]

H.-Q. Ma, S.-M. Wang, D. Zhang, J.-T. Chang, L.-L. Ji, Y.-X. Hou, and L.-A. Wu, “A Random number generator based on quantum entangled photon pairs,” Chin. Phys. Lett. 21, 1961–1964 (2004).
[CrossRef]

Mandel, L.

L. Mandel, “Quantum effects in one-photon and two-photon interference,” Rev. Mod. Phys. 71, S274–S282 (1999).
[CrossRef]

C. K. Hong and L. Mandel, “Experimental realization of a localized one-photon state,” Phys. Rev. Lett. 56, 58–60 (1986).
[CrossRef] [PubMed]

L. Mandel and E. Wolf, Optical Coherence and Quantum Optics (Cambridge Univ. Press, 1995).

Martín-Delgado, M. A.

A. Galindo and M. A. Martín-Delgado, “Information and computation: classical and quantum aspects,” Rev. Mod. Phys. 74, 347–423 (2002).
[CrossRef]

Medved Rogina, B.

M. Stipcevid and B. Medved Rogina, “Quantum random number generator based on photonic emission in semiconductors,” Rev. Sci. Instrum. 78, 045104 (2007).
[CrossRef]

Nechvatal, J.

A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, and S. Vo, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (revised),” Natl. Inst. Stand. Technol. (U. S.) Spec. Publ. 800-22rev1 (2008) http://csrc. nist. gov/groups/ST/toolkit/rng/documentation_software. html.

Peev, M.

V. Scarani, H. Bechmann-Pasquinucci, N. Cerf, M. Dusek, N. Lütkenhaus, and M. Peev, “The security of practical quantum key distribution,” Rev. Mod. Phys. 81, 1301–1350 (2009).
[CrossRef]

Peres, Y.

Y. Peres, “Iterating Von Neumann’s procedure for extracting random bits,” Ann. Stat. 20, 590–597 (1992).
[CrossRef]

Ribordy, G.

N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, “Quantum cryptography,” Rev. Mod. Phys. 74, 145–195 (2002).
[CrossRef]

Rukhin, A.

A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, and S. Vo, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (revised),” Natl. Inst. Stand. Technol. (U. S.) Spec. Publ. 800-22rev1 (2008) http://csrc. nist. gov/groups/ST/toolkit/rng/documentation_software. html.

Scarani, V.

V. Scarani, H. Bechmann-Pasquinucci, N. Cerf, M. Dusek, N. Lütkenhaus, and M. Peev, “The security of practical quantum key distribution,” Rev. Mod. Phys. 81, 1301–1350 (2009).
[CrossRef]

Scheel, S.

S. Scheel, “Single-photon sources—an introduction,” J. Mod. Opt. 56, 141–160 (2009).
[CrossRef]

Sharpe, A. W.

J. F. Dynes, Z. L. Yuan, A. W. Sharpe, and A. J. Shields, “A high speed, postprocessing free, quantum random number generator,” Appl. Phys. Lett. 93, 031109 (2008).
[CrossRef]

Shields, A. J.

J. F. Dynes, Z. L. Yuan, A. W. Sharpe, and A. J. Shields, “A high speed, postprocessing free, quantum random number generator,” Appl. Phys. Lett. 93, 031109 (2008).
[CrossRef]

Silverman, C. R.

M. P. Silverman, W. Strange, C. R. Silverman, and T. C. Lipscombe, “Tests for randomness of spontaneous quantum decay,” Phys. Rev. A 61, 042106 (2000).
[CrossRef]

M. P. Silverman, W. Strange, C. R. Silverman, and T. C. Lipscombe, “Tests of alpha-, beta-, and electron capture decays for randomness,” Phys. Lett. A 262, 265–273 (1999).
[CrossRef]

Silverman, M. P.

M. P. Silverman, W. Strange, C. R. Silverman, and T. C. Lipscombe, “Tests for randomness of spontaneous quantum decay,” Phys. Rev. A 61, 042106 (2000).
[CrossRef]

M. P. Silverman and W. Strange, “Experimental tests for randomness of quantum decay examined as a Markov process,” Phys. Lett. A 272, 1–9 (2000).
[CrossRef]

M. P. Silverman, W. Strange, C. R. Silverman, and T. C. Lipscombe, “Tests of alpha-, beta-, and electron capture decays for randomness,” Phys. Lett. A 262, 265–273 (1999).
[CrossRef]

Smid, M.

A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, and S. Vo, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (revised),” Natl. Inst. Stand. Technol. (U. S.) Spec. Publ. 800-22rev1 (2008) http://csrc. nist. gov/groups/ST/toolkit/rng/documentation_software. html.

Soto, J.

A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, and S. Vo, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (revised),” Natl. Inst. Stand. Technol. (U. S.) Spec. Publ. 800-22rev1 (2008) http://csrc. nist. gov/groups/ST/toolkit/rng/documentation_software. html.

Steane, A.

A. Steane, “Quantum computing,” Rep. Prog. Phys. 61, 117–173 (1998).
[CrossRef]

Stefanov, A.

A. Stefanov, N. Gisin, O. Guinnard, L. Guinnard, and H. Zbinden, “Optical quantum random number generator,” J. Mod. Opt. 47, 595–598 (2000).

Stipcevid, M.

M. Stipcevid and B. Medved Rogina, “Quantum random number generator based on photonic emission in semiconductors,” Rev. Sci. Instrum. 78, 045104 (2007).
[CrossRef]

Strange, W.

M. P. Silverman, W. Strange, C. R. Silverman, and T. C. Lipscombe, “Tests for randomness of spontaneous quantum decay,” Phys. Rev. A 61, 042106 (2000).
[CrossRef]

M. P. Silverman and W. Strange, “Experimental tests for randomness of quantum decay examined as a Markov process,” Phys. Lett. A 272, 1–9 (2000).
[CrossRef]

M. P. Silverman, W. Strange, C. R. Silverman, and T. C. Lipscombe, “Tests of alpha-, beta-, and electron capture decays for randomness,” Phys. Lett. A 262, 265–273 (1999).
[CrossRef]

Tittel, W.

N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, “Quantum cryptography,” Rev. Mod. Phys. 74, 145–195 (2002).
[CrossRef]

Umeno, K.

S.-J. Kim, K. Umeno, and A. Hasegawa, Corrections of the NIST Statistical Test Suite for Randomness Report 2004/018 (Cryptology ePrint Archive, 2004).

S.-J. Kim, K. Umeno, and A. Hasegawa, On the NIST Statistical Test Suite for RandomnessIEICE Tech. Rep. (IEICE, 2003) Vol. 103, 21–27.

Vangel, M.

A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, and S. Vo, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (revised),” Natl. Inst. Stand. Technol. (U. S.) Spec. Publ. 800-22rev1 (2008) http://csrc. nist. gov/groups/ST/toolkit/rng/documentation_software. html.

Vo, S.

A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, and S. Vo, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (revised),” Natl. Inst. Stand. Technol. (U. S.) Spec. Publ. 800-22rev1 (2008) http://csrc. nist. gov/groups/ST/toolkit/rng/documentation_software. html.

Von Neumann, J.

J. Von Neumann, “Various techniques used in connection with random digits,” Nat. Bur. Stand. (U. S.) Appl. Math Series No. 12 (GPO, 1951) pp. 36–38.

Wang, S.-M.

H.-Q. Ma, S.-M. Wang, D. Zhang, J.-T. Chang, L.-L. Ji, Y.-X. Hou, and L.-A. Wu, “A Random number generator based on quantum entangled photon pairs,” Chin. Phys. Lett. 21, 1961–1964 (2004).
[CrossRef]

Weihs, G.

T. Jennewein, U. Achleitner, G. Weihs, H. Weinfurter, and A. Zeilinger, “A fast and compact random number generator,” Rev. Sci. Instrum. 71, 1675–1680 (2000).
[CrossRef]

Weinberg, D. L.

D. C. Burnham and D. L. Weinberg, “Observation of simutaneity in parametric production of optical photon pairs,” Phys. Rev. Lett. 25, 84–87 (1970).
[CrossRef]

Weinfurter, H.

T. Jennewein, U. Achleitner, G. Weihs, H. Weinfurter, and A. Zeilinger, “A fast and compact random number generator,” Rev. Sci. Instrum. 71, 1675–1680 (2000).
[CrossRef]

Wolf, E.

L. Mandel and E. Wolf, Optical Coherence and Quantum Optics (Cambridge Univ. Press, 1995).

Wu, L.-A.

H.-Q. Ma, Y. Xie, and L.-A. Wu, “Random number generation based on the time of arrival of single photons,” Appl. Opt. 44, 7760–7763 (2005).
[CrossRef] [PubMed]

H.-Q. Ma, S.-M. Wang, D. Zhang, J.-T. Chang, L.-L. Ji, Y.-X. Hou, and L.-A. Wu, “A Random number generator based on quantum entangled photon pairs,” Chin. Phys. Lett. 21, 1961–1964 (2004).
[CrossRef]

Xie, Y.

Yuan, Z. L.

J. F. Dynes, Z. L. Yuan, A. W. Sharpe, and A. J. Shields, “A high speed, postprocessing free, quantum random number generator,” Appl. Phys. Lett. 93, 031109 (2008).
[CrossRef]

Zbinden, H.

N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, “Quantum cryptography,” Rev. Mod. Phys. 74, 145–195 (2002).
[CrossRef]

A. Stefanov, N. Gisin, O. Guinnard, L. Guinnard, and H. Zbinden, “Optical quantum random number generator,” J. Mod. Opt. 47, 595–598 (2000).

Zeilinger, A.

T. Jennewein, U. Achleitner, G. Weihs, H. Weinfurter, and A. Zeilinger, “A fast and compact random number generator,” Rev. Sci. Instrum. 71, 1675–1680 (2000).
[CrossRef]

A. Zeilinger, “Experiment and the foundations of quantum physics,” Rev. Mod. Phys. 71, S288–S297 (1999).
[CrossRef]

Zhang, D.

H.-Q. Ma, S.-M. Wang, D. Zhang, J.-T. Chang, L.-L. Ji, Y.-X. Hou, and L.-A. Wu, “A Random number generator based on quantum entangled photon pairs,” Chin. Phys. Lett. 21, 1961–1964 (2004).
[CrossRef]

Am. J. Phys. (1)

D. Branning, S. Bhandari, and M. Beck, “Low-cost coincidence-counting electronics for undergraduate quantum optics,” Am. J. Phys. 77, 667–670 (2009).
[CrossRef]

Ann. N.Y. Acad. Sci. (1)

T. Erber, “Testing the randomness of quantum mechanics: nature’s ultimate cryptogram?” Ann. N.Y. Acad. Sci. 755, 748–756 (1995).
[CrossRef]

Ann. Stat. (1)

Y. Peres, “Iterating Von Neumann’s procedure for extracting random bits,” Ann. Stat. 20, 590–597 (1992).
[CrossRef]

Appl. Opt. (1)

Appl. Phys. Lett. (1)

J. F. Dynes, Z. L. Yuan, A. W. Sharpe, and A. J. Shields, “A high speed, postprocessing free, quantum random number generator,” Appl. Phys. Lett. 93, 031109 (2008).
[CrossRef]

Chin. Phys. Lett. (1)

H.-Q. Ma, S.-M. Wang, D. Zhang, J.-T. Chang, L.-L. Ji, Y.-X. Hou, and L.-A. Wu, “A Random number generator based on quantum entangled photon pairs,” Chin. Phys. Lett. 21, 1961–1964 (2004).
[CrossRef]

J. Mod. Opt. (2)

A. Stefanov, N. Gisin, O. Guinnard, L. Guinnard, and H. Zbinden, “Optical quantum random number generator,” J. Mod. Opt. 47, 595–598 (2000).

S. Scheel, “Single-photon sources—an introduction,” J. Mod. Opt. 56, 141–160 (2009).
[CrossRef]

Phys. Lett. A (2)

M. P. Silverman, W. Strange, C. R. Silverman, and T. C. Lipscombe, “Tests of alpha-, beta-, and electron capture decays for randomness,” Phys. Lett. A 262, 265–273 (1999).
[CrossRef]

M. P. Silverman and W. Strange, “Experimental tests for randomness of quantum decay examined as a Markov process,” Phys. Lett. A 272, 1–9 (2000).
[CrossRef]

Phys. Rev. A (1)

M. P. Silverman, W. Strange, C. R. Silverman, and T. C. Lipscombe, “Tests for randomness of spontaneous quantum decay,” Phys. Rev. A 61, 042106 (2000).
[CrossRef]

Phys. Rev. Lett. (2)

D. C. Burnham and D. L. Weinberg, “Observation of simutaneity in parametric production of optical photon pairs,” Phys. Rev. Lett. 25, 84–87 (1970).
[CrossRef]

C. K. Hong and L. Mandel, “Experimental realization of a localized one-photon state,” Phys. Rev. Lett. 56, 58–60 (1986).
[CrossRef] [PubMed]

Rep. Prog. Phys. (1)

A. Steane, “Quantum computing,” Rep. Prog. Phys. 61, 117–173 (1998).
[CrossRef]

Rev. Mod. Phys. (5)

A. Galindo and M. A. Martín-Delgado, “Information and computation: classical and quantum aspects,” Rev. Mod. Phys. 74, 347–423 (2002).
[CrossRef]

L. Mandel, “Quantum effects in one-photon and two-photon interference,” Rev. Mod. Phys. 71, S274–S282 (1999).
[CrossRef]

A. Zeilinger, “Experiment and the foundations of quantum physics,” Rev. Mod. Phys. 71, S288–S297 (1999).
[CrossRef]

N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, “Quantum cryptography,” Rev. Mod. Phys. 74, 145–195 (2002).
[CrossRef]

V. Scarani, H. Bechmann-Pasquinucci, N. Cerf, M. Dusek, N. Lütkenhaus, and M. Peev, “The security of practical quantum key distribution,” Rev. Mod. Phys. 81, 1301–1350 (2009).
[CrossRef]

Rev. Sci. Instrum. (2)

M. Stipcevid and B. Medved Rogina, “Quantum random number generator based on photonic emission in semiconductors,” Rev. Sci. Instrum. 78, 045104 (2007).
[CrossRef]

T. Jennewein, U. Achleitner, G. Weihs, H. Weinfurter, and A. Zeilinger, “A fast and compact random number generator,” Rev. Sci. Instrum. 71, 1675–1680 (2000).
[CrossRef]

Other (7)

A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, and S. Vo, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (revised),” Natl. Inst. Stand. Technol. (U. S.) Spec. Publ. 800-22rev1 (2008) http://csrc. nist. gov/groups/ST/toolkit/rng/documentation_software. html.

L. Mandel and E. Wolf, Optical Coherence and Quantum Optics (Cambridge Univ. Press, 1995).

There is an error in the current NIST publication concerning this test: in section , although all of the formulae appear to be correct, the last three tables of probabilities (for M=512, 1000, and 10000) are not. The source code for the Statistical Test Suite provided by NIST, to the extent that it makes use of these incorrect probabilities, is also in error.

S.-J. Kim, K. Umeno, and A. Hasegawa, On the NIST Statistical Test Suite for RandomnessIEICE Tech. Rep. (IEICE, 2003) Vol. 103, 21–27.

S.-J. Kim, K. Umeno, and A. Hasegawa, Corrections of the NIST Statistical Test Suite for Randomness Report 2004/018 (Cryptology ePrint Archive, 2004).

The current NIST publication also contains an error regarding this test: on page 2–32, Eq. , the absolute value of Sk should be divided by n.

J. Von Neumann, “Various techniques used in connection with random digits,” Nat. Bur. Stand. (U. S.) Appl. Math Series No. 12 (GPO, 1951) pp. 36–38.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (20)

Fig. 1
Fig. 1

Experimental arrangement for measuring single-photon polarizations. Signal and idler photon pairs are created in the PDC and counted in coincidence either at detectors AB or A B , depending on the measurement outcome for the diagonally polarized idler photon in the H–V basis. A binary sequence is created by assigning “0” to the coincidence events AB and “1” to the events A B .

Fig. 2
Fig. 2

Numbers of coincidence counts per 0.1 ms time bin. Roughly 25% of the bins contained exactly one coincidence count. These events were used to construct the binary sequence for testing.

Fig. 3
Fig. 3

P-values for the Bias Test. Each of the 170 sub-sequences produced one p-value. The white space in the first bin represents the five sequences, or 2.94% of them, which failed at the 0.01 level ( p 0.01 ) . This was significantly more than the one or two failures expected at this level, indicating that the source was not perfectly unbiased.

Fig. 4
Fig. 4

P-values for the Block Bias Test, which produced nine p-values for each of the 170 sub-sequences. Sixteen of the 1530 p-values, or 1.05% of them, were below 0.01.

Fig. 5
Fig. 5

P-values for the Number of Runs Test. P-values for two of the sub-sequences, or 1.18% of them, were below 0.01.

Fig. 6
Fig. 6

P-values for the Longest Run of Ones in a Block Test. The test generated five p-values for each sub-sequence. Eleven of these 850 p-values, or 1.29% of them, were below 0.01.

Fig. 7
Fig. 7

P-values for the Binary Matrix Rank Test. There were no p-values below 0.01.

Fig. 8
Fig. 8

P-values for the Discrete Fourier Transform Test. P-values for three of the sub-sequences, or 1.76% of them, were below 0.01.

Fig. 9
Fig. 9

P-values for the Approximate Entropy Test. P-values for two of the sub-sequences, or 1.18% of them, were below 0.01.

Fig. 10
Fig. 10

P-values for the Serial Patterns Test. The test produced two p-values for each sub-sequence. Four of the 340 p-values, or 1.18% of them, were below 0.01.

Fig. 11
Fig. 11

P-values for the Cumulative Sums Test. The test produced two p-values for each sub-sequence. The average is p = 0.4799 . Twelve of the 340 p-values, or 3.53% of them, were below 0.01.

Fig. 12
Fig. 12

P-values for the Non-Overlapping Template Match Test. The P-value for one sub-sequence, or 0.588% of them, was below 0.01.

Fig. 13
Fig. 13

P-values for the Random Excursions Test. The test generated eight p-values for each of the 17 sub-sequences tested. Thirteen of these 136 p-values, or 9.56% of them, were less than 0.1 (shown in white).

Fig. 14
Fig. 14

P-values for the Random Excursions Variant Test. This test generated 18 p-values per sub-sequence. Seventeen of these 306 p-values, or 5.56% of them, were below 0.1.

Fig. 15
Fig. 15

P-values for the Overlapping Runs of Ones Test. The average is p = 0.349 (solid line) and the standard deviation is 0.197. Only the first sub-sequence has a p-value below 0.1.

Fig. 16
Fig. 16

P-values for Maurer’s Universal Statistical Test. The average is p = 0.485 (solid line) and the standard deviation is 0.286. Only the final sub-sequence (number 17) has a p-value below 0.1.

Fig. 17
Fig. 17

P-values for the Linear Complexity Test. The average is p = 0.603 (solid line) and the standard deviation is 0.259. Only sub-sequence 5 produced a p-value below 0.1.

Fig. 18
Fig. 18

Proportion of 170 sequences passing the first ten tests at a confidence threshold of 0.01. The outlying points for tests 1 and 9 are due to the bias of the source.

Fig. 19
Fig. 19

Proportion of 17 sequences passing the final five tests at a confidence threshold of 0.1.

Fig. 20
Fig. 20

Histogram of all p-values generated from the NIST Test Suite. Ideally, the p-values follow a uniform distribution.

Equations (12)

Equations on this page are rendered with MathJax. Learn more.

| ψ = M | vac + η | H s | H i ,
f = ( 1 α ) ± 3 α ( 1 α ) s ,
x = 0 1 x p ( x ) d x = 1 2 ,
x 2 = 0 1 x 2 p ( x ) d x = 1 3 ,
σ x = x 2 x 2 = 0.289 .
P R = 1 P T = cos 2 ( 2 θ )
d P R d θ = d d θ [ cos 2 ( 2 θ ) ] θ = π 8 = 2 .
δ P R δ θ d P R d θ 0.01 ,
p = erfc ( | s | 2 n ) = erfc ( z ) .
z = | s | 2 n
z repeat = | 2 s | 2 ( 2 n ) = 2 2 | s | 2 n = 2 z .
z repeat + mixed = | 2 s | 2 ( 4 n ) = | s | 2 n = z .

Metrics