Certifiable quantum dice: Or, true random number generation secure against quantum adversaries
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.
Cite this item
Vazirani, U., & Vidick, T. (2012). Certifiable quantum dice: Or, true random number generation secure against quantum adversaries. STOC ’12: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, 61–76. https://doi.org/10.1145/2213977.2213984
Click Copy to copy the citation, or select the text manually.
2-s2.0-84862620607
Computer Science Division
California Institute of Technology
2012
New York
9781450312455
61
76
REVIEWED
OTHER
| Event name | Event acronym | Event place | Event date |
STOC'12 | New York, United States | 2012-05-19 - 2012-05-22 | |