Abstract:

In this work, we introduce {\it one-time programs}, a new computational paradigm geared towards security applications. A one-time 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 one-time 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 One-time 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 one-time computing opens new avenues for conceptual research. In this work 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 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 one-time program. We also show how this memory device can be used to construct one-time proofs. Specifically, we show how to use this device to efficiently convert a classical witness for any $NP$ statement, into ''one-time proof'' for that statement. We show that such our hardware-based solution is provably secure against all `computational side-channel attacks' which we will define in the talk.

This is joint work with Guy Rothblum and Yael Kalai

Biography:

    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 fault-tolerant 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).