Quantum one-time programs



Playing this video requires the latest flash player from Adobe.

Download link (right click and 'save-as') for playing in VLC or other f4v compatible player.


Recording Details

Speaker(s): 
Scientific Areas: 
Collection/Series: 
PIRSA Number: 
12120028

Abstract

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