A one-time program is a hypothetical device by which a user may evaluate a circuit on exactly one input of his choice, before the device self-destructs. One-time programs cannot be achieved by software alone, as any software can be copied and re-run. However, it is known that every circuit can be compiled into a one-time program using a very basic hypothetical hardware device called a one-time memory. At first glance it may seem that quantum information, which cannot be copied, might also allow for one-time programs. But it is not hard to see that this intuition is false: one-time programs for classical or quantum circuits based solely on quantum information do not exist, even with computational assumptions.
Program obfuscation A related but different task is program obfuscation, in which the receiver should not be able to efficiently learn'' anything from the description of the program that he could not also efficiently learn from the input-output behaviour of the program. In the case of classical information, it is known that secure program obfuscation is not possible in the plain model @cite_7 . As with copy-protection, OTPs provide a hardware solution by enforcing that the obfuscated program can be run only a limited number of times. Again, the more interesting question is if quantum information alone (with computational assumptions) can provide a solution; the impossibility proof for obfuscation breaks down in the quantum case due to the no-cloning theorem. It is an open problem whether there is a way to substitute the assumption of secure hardware in our main possibility result with a computational assumption in order to realize quantum program obfuscation.
@cite_7
2084641398
Informally, an obfuscator O is an (efficient, probabilistic) “compiler” that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is “unintelligible” in some sense. Obfuscators, if they exist, would have a wide variety of cryptographic and complexity-theoretic applications, ranging from software protection to homomorphic encryption to complexity-theoretic analogues of Rice's theorem. Most of these applications are based on an interpretation of the “unintelligibility” condition in obfuscation as meaning that O(P) is a “virtual black box,” in the sense that anything one can efficiently compute given O(P), one could also efficiently compute given oracle access to P. In this work, we initiate a theoretical investigation of obfuscation. Our main result is that, even under very weak formalizations of the above intuition, obfuscation is impossible. We prove this by constructing a family of efficient programs P that are unobfuscatable in the sense that (a) given any efficient program P' that computes the same function as a program P ∈ p, the “source code” P can be efficiently reconstructed, yet (b) given oracle access to a (randomly selected) program P ∈ p, no efficient algorithm can reconstruct P (or even distinguish a certain bit in the code from random) except with negligible probability. We extend our impossibility result in a number of ways, including even obfuscators that (a) are not necessarily computable in polynomial time, (b) only approximately preserve the functionality, and (c) only need to work for very restricted models of computation (TC0). We also rule out several potential applications of obfuscators, by constructing “unobfuscatable” signature schemes, encryption schemes, and pseudorandom function families.