Title: One Time Programs  
Name: Shafi Goldwasser MIT and Weizmann Institute 

Time:October 14th (Tuesday)?09:1510:00  
Location: Lecture Hall, FIT Building, Tsinghua University  
Host Unit: ITCS, Tsinghua University 
In this work, we introduce {\it onetime programs}, a new computational paradigm geared towards security applications. A onetime program can be executed on a {\em single} input, whose value can be specified at run time. Other than the result of the computation on this input, nothing else about the program is leaked. Hence, a onetime program is like a black box function that may be evaluated once and then ``self destructs.'' This also extends to $k$time programs, which are like black box functions that can be evaluated $k$ times and then self destruct.
The applications of Onetime programs include temporary transfer of cryptographic ability, as well as? electronic cash or token schemes: coins are generated by a program that can only be run once, and thus cannot be double spent. Most significantly, the new paradigm of onetime computing opens new avenues for conceptual research. In this work we explore one such avenue, presenting the new concept of ``onetime proofs,'' proofs that can only be verified once and then become useless and unconvincing.
All these tasks are clearly 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. All our solutions employ a secure memory device, inspired by the cryptographic notion of interactive oblivious transfer protocols, that stores two secret keys ($k_0,k_1$). The device takes as input a single bit $b \in \zo$, outputs $k_b$, and then self destructs. Using such devices, we demonstrate that for every input length, any standard program (Turing machine) can be efficiently compiled into a functionally equivalent onetime program. We also show how this memory device can be used to construct onetime proofs. Specifically,? we show how to use this device to efficiently convert a classical witness for any $NP$ statement, into ''onetime proof'' for that statement. We show that such our hardwarebased solution are provably secure against all `computational sidechannel attacks' which we will define in the talk.
This is joint work with Guy Rothblum and Yael Kalai
Shafi Goldwasser is the RSA professor of computer science in the Massachusetts Institute of Technology, and a professor of computer science and applied mathematics in the Weizmann Institute of science in Israel. She received a B.S. (1979) in Mathematics from Carnegie Mellon University, and an M.S. (1981) and Ph.D (1983) in computer science from the University of California at Berkeley.
Professor Goldwasser's research interests include cryptography, computational number theory, complexity theory, probabilistic algorithms, and faulttolerant distributed computation.
Professor Goldwasser is a recipient of the NSF Presidential Young Investigator Award of 1987, and the NSF Faculty Award for Women of 1991. She received a first G\"{o}del Prize in 1993 for her paper on ''The Knowledge Complexity of Interactive Proofs,'' and a second G\"{o}del Prize in 2001 for her paper on "Interactive Proofs and the Hardness of Approximating Cliques". She is the recipient of the 1996 ACM Grace Murray Hopper Award for outstanding young computer professional of the year, the 1998 winner of the RSA award for Mathematics. She was selected as a fellow of the international association for cryptologic research in 2007, and is the winner of the 2008 ACM Athena award.
Professor Goldwasser is a member of the American Academy of Arts and Science since 2001, a member of the National Academy of Science 2004, a member of the National Academy of Engineering 2004, and is the first holder of the RSA Professorship which was established in 1997. She has been a plenary speaker in numerous conferences, including the International Congress of Mathematics (ICM) at 2002 (and a section speaker at ICM 1992), the International Symposium on Information Theory (ISIT) 2002, the Federated Computing Research Conference (FCRC) 1999, the Foundation of Computer Science Conference (1997), and the Principles of Distributed Computing Conference (1997).