Douglas Stebila

Quantum one-time programs

Abstract

A one-time program is a hypothetical device by which a user may evaluate a circuit on exactly one input of his choice, before the device self-destructs. One-time programs cannot be achieved by software alone, as any software can be copied and re-run. However, it is known that every circuit can be compiled into a one-time program using a very basic hypothetical hardware device called a one-time memory. At first glance it may seem that quantum information, which cannot be copied, might also allow for one-time programs. But it is not hard to see that this intuition is false: one-time programs for classical or quantum circuits based solely on quantum information do not exist, even with computational assumptions.

This observation raises the question, “what assumptions are required to achieve one-time programs for quantum circuits?” Our main result is that any quantum circuit can be compiled into a one-time program assuming only the same basic one-time memory devices used for classical circuits. Moreover, these quantum one-time programs achieve statistical universal composability (UC-security) against any malicious user. Our construction employs methods for computation on authenticated quantum data, and we present a new quantum authentication scheme called the trap scheme for this purpose. As a corollary, we establish UC-security of a recent protocol for delegated quantum computation.

Keywords: quantum cryptography, one-time programs

Reference

Anne Broadbent, Gus Gutoski, Douglas Stebila. Quantum one-time programs. In Ran Canetti, Juan Garay, editors, Advances in Cryptology -- Proc. CRYPTO 2013, LNCS, vol. 8043, pp. 344-360. Springer, August 2013. © IACR.

Download

Presentations

• 2013-08-22: CRYPTO 2013. (PDF slides)

BibTeX

@inproceedings{C:BroGutSte13,
 	Author = {Anne Broadbent and Gus Gutoski and Douglas Stebila},
 	Booktitle = {Advances in Cryptology -- Proc. {CRYPTO} 2013},
 	Doi = {10.1007/978-3-642-40084-1\_20},
 	Editor = {Ran Canetti and Juan Garay},
 	Month = {August},
 	Pages = {344--360},
 	Publisher = {Springer},
 	Series = {LNCS},
 	Title = {Quantum one-time programs},
 	Volume = {8043},
 	Year = {2013}
 }

Funding

• Australian Research Council (ARC) Discovery Project grant DP130104304
• Canadian Institute for Advanced Research (CIFAR)
• DTO-ARO
• Industry Canada
• Natural Sciences and Enginering Research Council (NSERC) of Canada
• Ontario Ministry of Research and Innovation
• QuantumWorks