Search

I survey some of the recent progress on software obfuscation spurred by the exciting paper of Garg, Gentry, Halevi, Raykova, Sahai and Waters [GGH13]. This is a preprint version of a review article [Bar16] appearing in the Communications of the ACM. That article was written for a general computing audience, and is also not up to date on the latest research in this fast-moving field since it was mostly written in 2014. Nevertheless, I thought it might still be of interest to cryptographers. Computer programs are arguably the most complex objects ever constructed by humans. Even understanding a 10-line program such as the one depicted in Figure 1 can be extremely difficult. The complexity of programs has been the bane (as well as the boon) of the software industry, and taming it has been the objective of many efforts in industry and academia. Given this, it is not surprising that both theoreticians and practitioners have been trying to “harness this complexity for good” and use it to protect sensitive information and computation. In its most general form this is known as software obfuscation, and it is the topic of this survey. In a certain sense, any cryptographic tool such as encryption or authentication can be thought of harnessing complexity for security, but with software obfuscation people have been aiming for something far more ambitious: a way to transform arbitrary programs into an “inscrutable” or obfuscated form. By this we don’t mean that reverse engineering the program should be cumbersome but rather that it should be infeasible, in the same way that recovering the plaintext of a secure encryption cannot be performed using any reasonable amount of resources. ∗Harvard John A. Paulson School of Engineering and Applied Sciences, b@boazbarak.org. This article was written while the author was at Microsoft Research

This paper introduces notions from computational complexity into the study of financial derivatives. Traditional economics argues that derivatives, like CDOs and CDSs, ameliorate the negative costs imposed due to asymmetric information between buyers and sellers. This is because securitization via these derivatives allows the informed party to find buyers for the information-insensitive part of the cash flow stream of an asset (e.g., a mortgage) and retain the remainder. In this paper we show that this viewpoint may need to be revised once computational complexity is brought into the picture. Assuming reasonable complexity-theoretic conjectures, we show that derivatives can actually amplify the costs of asymmetric information instead of reducing them. We prove our results both in the worst-case setting, as well as the more realistic average case setting. In the latter case, to argue that our constructions result in derivatives that “look like” real-life derivatives, we use the notion of computational indistinguishability a la cryptography.