One-Time Programs
Speaker: Guy Rothblum , CSAIL, MIT
Date: March 14 2008
Time: 10:30AM to 12:00PM
Location: 32--G449
Host: Shafi Goldwasser, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
In this work we introduce one-time programs, a new computational paradigm geared towards security applications. A one-time program is a program that can be executed on a single input, specified by the user at run time. Nothing is leaked about the program's code or functionality except its output on this single input. Hence, a one-time program is like a ``black box'' function that may be evaluated once and then ``self destructs''. This concept easily extends to k-time programs, which are like black box functions that can be evaluated k times before they self destruct.
One-time programs serve many of the same purposes of program obfuscation, the obvious one being software protection. However, the applications of one-time programs go beyond those of obfuscation. One-time programs only allow a user to learn the program's output on a bounded number of inputs, whereas obfuscated programs can be run an arbitrary number of times. For example, one-time programs lead naturally to electronic cash or token schemes: coins are generated by a program that can only be run once, and thus cannot be double spent.
Moreover, the new paradigm of one-time computing opens new avenues for conceptual research. We explore one such avenue, presenting the new concept of ``one-time proofs'', proofs that can only be verified once and then become useless and unconvincing.
All the above tasks are impossible using software alone, as any piece of software can be copied and run again, enabling the user to execute the program on more than one input. Our solutions employ a very simple and cheap secure hardware device. We show that any standard program (Turing Machine) can be efficiently compiled into a functionally equivalent one-time program that employs this simple hardware device. We can similarly transform a classic NP witness for a statement into a one-time proof for the statement, this one-time proof employs the same hardware device.
Joint work with Shafi Goldwasser and Yael Kalai
See other events that are part of Cryptography and Information Security Seminars 2007/2008
See other events happening in March 2008
