Quantum one-time programs


Gutowski, G. (2012). Quantum one-time programs. Perimeter Institute. https://pirsa.org/12120028


Gutowski, Gus. Quantum one-time programs. Perimeter Institute, Dec. 06, 2012, https://pirsa.org/12120028


          @misc{ pirsa_PIRSA:12120028,
            doi = {10.48660/12120028},
            url = {https://pirsa.org/12120028},
            author = {Gutowski, Gus},
            keywords = {Quantum Information},
            language = {en},
            title = {Quantum one-time programs},
            publisher = {Perimeter Institute},
            year = {2012},
            month = {dec},
            note = {PIRSA:12120028 see, \url{https://pirsa.org}}

Gus Gutowski Institute for Quantum Computing (IQC)


A "one-time program" for a channel C is a hypothetical cryptographic primitive by which a user may evaluate C on only one input state of her choice.  (Think Mission Impossible: "this tape will self-destruct in five seconds.")  One-time programs cannot be achieved without extra assumptions such as secure hardware; it is known that one-time programs can be constructed for classical channels using a very basic hypothetical hardware device called a "one-time memory".   Our main result is the construction of a one-time program for any quantum channel specified by a circuit, assuming the same basic one-time memory devices used for classical channels.  The construction achieves universal composability -- the strongest possible security -- against any quantum adversary.  It employs a technique for computation on authenticated quantum data and we present a new authentication scheme called the "trap" scheme for this purpose.   Finally, we observe that there is a pathological class of channels that admit trivial one-time programs without any hardware assumptions whatsoever.  We characterize these channels, assuming an interesting conjecture on the invertible (or decoherence-free) subspaces of an arbitrary channel.   Joint work with Anne Broadbent and Douglas Stebila. http://arxiv.org/abs/1211.1080