- Home »
- Quantum one-time programs

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.

Event Type:

Seminar

Collection/Series:

Scientific Area(s):

Speaker(s):

Event Date:

Thursday, December 6, 2012 - 14:30 to 16:00

Location:

Alice Room

©2012 Perimeter Institute for Theoretical Physics