A Caltech Library Service

Certifiable Quantum Dice Or, True Random Number Generation Secure Against Quantum Adversaries

Vazirani, Umesh and Vidick, Thomas (2012) Certifiable Quantum Dice Or, True Random Number Generation Secure Against Quantum Adversaries. In: STOC'12 Symposium on Theory of Computing Conference. ACM , New York, NY, pp. 61-76. ISBN 978-1-4503-1245-5.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We introduce a protocol through which a pair of quantum mechanical devices may be used to generate n bits that are ε-close in statistical distance from n uniformly distributed bits, starting from a seed of O(log n log 1/ε) uniform bits. The bits generated are certifiably random based only on a simple statistical test that can be performed by the user, and on the assumption that the devices do not communicate in the middle of each phase of the protocol. No other assumptions are placed on the devices' inner workings. A modified protocol uses a seed of O(log^3 n) uniformly random bits to generate n bits that are poly^(-1)(n)-indistinguishable from uniform even from the point of view of a quantum adversary who may have had prior access to the devices, and may be entangled with them.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2012 ACM New York. We thank Matthew Coudron for useful comments on a preliminary draft of this paper. Supported by NIST award No. 60NANB10D262, ARO Grant W911NF-09-1-0440 and NSF Grant CCF-0905626 Supported by NSF Grant 0844626. Part of this work was completed while at UC Berkeley, supported by ARO Grant W911NF-09-1-0440 and NSF Grant CCF-0905626.
Funding AgencyGrant Number
National Institute of Standards & Technology (NIST)60NANB10D262
Army Research Office (ARO)W911NF-09-1-0440
Subject Keywords:Certifiable Randomness, Quantum Computing, Entanglement, Random Number Generator
Record Number:CaltechAUTHORS:20140910-141425231
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:49557
Deposited By: Ruth Sustaita
Deposited On:10 Sep 2014 21:41
Last Modified:10 Nov 2021 18:45

Repository Staff Only: item control page