Hiding secrets in software: a cryptographic approach to program obfuscation

Abstract

Can we hide secrets in software? Can we obfuscate programs---that is, make programs unintelligible while preserving their functionality? What exactly do we mean by "unintelligible"? Why would we even want to do this?

In this article, we describe some rigorous cryptographic answers to these quasi-philosophical questions. We also discuss our recent "candidate indistinguishability obfuscation" scheme and its implications.

References

1. Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., Yang, K. On the (im)possibility of obfuscating programs. In CRYPTO (2001). Springer, 1--18.
2. Barrington, D.A. Bounded-width polynomial-size branching programs recognize exactly those languages in nc¹. In STOC (1986). ACM, 1--5.
3. Boneh, D., Sahai, A., Waters, B. Functional encryption: Definitions and challenges. In Theory of Cryptography Conference (TCC) (2011). Springer, 253--273.
4. Brakerski, Z., Vaikuntanathan, V. Efficient fully homomorphic encryption from (standard) lwe. SIAM J. Comput. 43, 2 (2014), 831--871.
5. Brakerski, Z., Vaikuntanathan, V. Lattice-based FHE as secure as PKE. In Innovations in Theoretical Computer Science (ITCS) (2014), ACM, 1--12.
6. Collberg, C., Nagra, J. Surreptitious Software: Obfuscation, Watermarking, and Tamperproofing for Software Protection, 1st ed. Addison-Wesley Professional, Boston, MA, 2009.
7. Coron, J.-S., Lepoint, T., Tibouchi, M. Practical multilinear maps over the integers. In CRYPTO (2013). Springer, 476--493.
8. Diffie, W., Hellman, M.E. New directions in cryptography. IEEE Trans. Inform. Theory 22, 6 (1976), 644--654.
9. Feige, U., Shamir, A. Zero knowledge proofs of knowledge in two rounds. In CRYPTO'89 (1990). Springer 526--544.
10. Garg, S., Gentry, C., Halevi, S. Candidate multilinear maps from ideal lattices. In EUROCRYPT (2013). Springer, 1--17.
11. Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B. Candidate indistinguishability obfuscation and functional encryption for all circuits. In FOCS (2013). IEEE, 40--49.
12. Garg, S., Gentry, C., Sahai, A., Waters, B. Witness encryption and its applications. In STOC (2013). ACM, 467--476.
13. Gentry, C. A fully homomorphic encryption scheme. PhD thesis, Stanford University (2009). crypto. stanford.edu/craig.
14. Gentry, C. Computing arbitrary functions of encrypted data. Commun. ACM53, 3 (2010), 97--105.
15. Gentry, C., Gorbunov, S., Halevi, S. Graph-induced multilinear maps from lattices. In Theory of Cryptography Conference (TCC) (2015). Springer 498--527.
16. Gentry, C., Sahai, A., Waters, B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In CRYPTO (2013). Springer, 75--92.
17. Goldwasser, S., Kalai, Y.T. On the impossibility of obfuscation with auxiliary input. In FOCS (2005). IEEE, 553--562.
18. Goldwasser, S., Micali, S. Probabilistic encryption. J. Comput. Syst. Sci. 28, 2 (1984), 270--299.
19. Goldwasser, S., Rothblum, G.N. On best-possible obfuscation. In Theory of Cryptography Conference (TCC) (2007). Springer, 194--213.
20. Hada, S. Zero-knowledge and code obfuscation. In ASIACRYPT (2000). Springer, 443--457.
21. Kilian, J. Founding cryptography on oblivious transfer. In STOC (1988). ACM, 20--31.
22. Naor, M., Yung, M. Public-key cryptosystems provably secure against chosen ciphertext attacks. In STOC (1990). ACM, 427--437.
23. Rivest, R., Adleman, L., Dertouzos, M.L. On data banks and privacy homomorphisms. In Foundations of Secure Computation (1978), 169--180.
24. Sahai, A. Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In FOCS (1999). IEEE, 543--553.
25. Sahai, A., Waters, B. Fuzzy identity-based encryption. In EUROCRYPT (2005). Springer, 457--473.
26. Sahai, A., Waters, B. How to use indistinguishability obfuscation: Deniable encryption, and more. In STOC (2014). ACM, 475--484.

Index Terms

• Security and privacy

  • Cryptography

  • Systems security

    • Operating systems security

• Theory of computation

  • Computational complexity and cryptography

    • Problems, reductions and completeness