Indistinguishability Obfuscation from Functional Encryption

Abstract

Indistinguishability obfuscation (IO) is a tremendous notion, powerful enough to give rise to almost any known cryptographic object. Prior candidate IO constructions were based on specific assumptions on algebraic objects called multi-linear graded encodings.

We present a generic construction of indistinguishability obfuscation from public-key functional encryption with succinct encryption circuits and subexponential security. This shows the equivalence of indistinguishability obfuscation and public-key functional encryption, a primitive that has previously seemed to be much weaker, lacking the power and the staggering range of applications of indistinguishability obfuscation.

Our main construction can be based on functional encryption schemes that support a single functional key, and where the encryption circuit grows sub-linearly in the circuit-size of the function. We further show that sublinear succinctness in circuit-size for single-key schemes can be traded with sublinear succinctness in the number of keys (also known as the collusion-size) for multi-key schemes. We also show that, under the Learning with Errors assumption, our techniques imply that any indistinguishability obfuscator can be converted into one where the size of obfuscated circuits is twice that of the original circuit plus an additive overhead that is polynomial in its depth, input length, and the security parameter.

References

1. Shweta Agrawal, David Mandell Freeman, and Vinod Vaikuntanathan. 2011. Functional encryption for inner product predicates from learning with errors. In Proceedings of the 17th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT’11) (Lecture Notes in Computer Science), Dong Hoon Lee and Xiaoyun Wang (Eds.), Vol. 7073. Springer, 21--40.
2. Shweta Agrawal, Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. 2013. Functional encryption: New perspectives and lower bounds, see Reference Canetti and Garay {28}, 500--518.
3. Prabhanjan Ananth, Zvika Brakerski, Gil Segev, and Vinod Vaikuntanathan. 2015. The Trojan method in functional encryption: From selective to adaptive security, generically. In Proceedings of the Annual International Cryptology Conference (CRYPTO’15).
4. Prabhanjan Ananth and Abhishek Jain. 2015. Indistinguishability obfuscation from compact functional encryption. In Proceedings of the Annual International Cryptology Conference (CRYPTO’15).
5. Prabhanjan Ananth, Abhishek Jain, and Amit Sahai. 2015. Achieving compactness generically: Indistinguishability obfuscation from non-compact functional encryption. IACR Cryptol. ePrint Arch. 2015 (2015), 730. http://eprint.iacr.org/2015/730.
6. Prabhanjan Ananth, Abhishek Jain, and Amit Sahai. 2017. Indistinguishability obfuscation for turing machines: Constant overhead and amortization. In Proceedings of the 37th Annual International Cryptology Conference (CRYPTO’17). 252--279.
7. Prabhanjan Ananth and Amit Sahai. 2017. Projective arithmetic functional encryption and indistinguishability obfuscation from degree-5 multilinear maps. In Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’17). 152--181.
8. Benny Applebaum and Zvika Brakerski. 2015. Obfuscating circuits via composite-order graded encoding. In Proceedings of the Theory of Cryptography Conference (TCC’15).
9. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. 2004. Cryptography in NC⁰. In Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS’04). 166--175.
10. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. 2006. Computationally private randomizing polynomials and their applications. Comput. Complex. 15, 2 (2006), 115--162.
11. Benny Applebaum, Yuval Ishai, Eyal Kushilevitz, and Brent Waters. 2013. Encoding functions with constant online rate or how to compress garbled circuits keys, see Reference Canetti and Garay {28}, 166--184.
12. Boaz Barak, Sanjam Garg, Yael Tauman Kalai, Omer Paneth, and Amit Sahai. 2014. Protecting obfuscation against algebraic attacks. In Proceedings of the 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’14). 221--238.
13. Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. 2012. On the (im)possibility of obfuscating programs. J. ACM 59, 2 (2012), 6.
14. Nir Bitansky, Ran Canetti, Henry Cohn, Shafi Goldwasser, Yael Tauman Kalai, Omer Paneth, and Alon Rosen. 2014. The impossibility of obfuscation with auxiliary input or a universal simulator. In Proceedings of the Annual International Cryptology Conference (CRYPTO’14). 71--89.
15. Nir Bitansky, Sanjam Garg, Huijia Lin, Rafael Pass, and Sidharth Telang. 2015. Succinct randomized encodings and their applications. In Proceedings of the Symposium on Theory of Computing (STOC’15).
16. Nir Bitansky, Ryo Nishimaki, Alain Passelègue, and Daniel Wichs. 2016. From cryptomania to obfustopia through secret-key functional encryption. IACR Cryptol. ePrint Arch. 2016 (2016), 558. Retrieved from http://eprint.iacr.org/2016/558.
17. Andrej Bogdanov and Alon Rosen. 2017. Pseudorandom functions: Three decades later. In Tutor. Found. Cryptogr. 79--158.
18. Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, and Giuseppe Persiano. 2004. Public key encryption with keyword search. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’04). 506--522.
19. Dan Boneh, Craig Gentry, Sergey Gorbunov, Shai Halevi, Valeria Nikolaenko, Gil Segev, Vinod Vaikuntanathan, and Dhinakaran Vinayagamurthy. 2014. Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits. In Proceedings of the 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’14). 533--556.
20. Dan Boneh, Amit Sahai, and Brent Waters. 2012. Functional encryption: A new vision for public-key cryptography. Commun. ACM 55, 11 (2012), 56--64.
21. Dan Boneh and Brent Waters. 2013. Constrained pseudorandom functions and their applications. In Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT’13) (Lecture Notes in Computer Science), Kazue Sako and Palash Sarkar (Eds.), Vol. 8270. Springer, 280--300.
22. Elette Boyle, Kai-Min Chung, and Rafael Pass. 2014. On extractability obfuscation. In Proceedings of the Theory of Cryptography Conference (TCC’14). 52--73.
23. Elette Boyle, Shafi Goldwasser, and Ioana Ivan. 2014. Functional signatures and pseudorandom functions. In Proceedings of the International Conference on Practice and Theory of Public Key Cryptography (PKC’14) (Lecture Notes in Computer Science), Hugo Krawczyk (Ed.), Vol. 8383. Springer, 501--519.
24. Zvika Brakerski, Ilan Komargodski, and Gil Segev. 2016. Multi-input functional encryption in the private-key setting: Stronger security from weaker assumptions. In Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’16). 852--880.
25. Zvika Brakerski and Guy N. Rothblum. 2014. Virtual black-box obfuscation for all circuits via generic graded encoding. In Proceedings of the 11th Theory of Cryptography Conference (TCC’14) (Lecture Notes in Computer Science), Yehuda Lindell (Ed.), Vol. 8349. Springer, 1--25.
26. Zvika Brakerski and Gil Segev. 2015. Function-private functional encryption in the private-key setting. In Proceedings of the Theory of Cryptography Conference (TCC’15).
27. Ran Canetti. 1997. Towards realizing random oracles: Hash functions that hide all partial information. In Proceedings of the 17th Annual International Cryptology Conference (CRYPTO’97) (Lecture Notes in Computer Science), Burton S. Kaliski Jr. (Ed.), Vol. 1294. Springer, 455--469.
28. Ran Canetti and Juan A. Garay (Eds.). 2013. Proceedings of the 33rd Annual Cryptology Conference (CRYPTO’13). Lecture Notes in Computer Science, Vol. 8043. Springer.
29. Ran Canetti, Justin Holmgren, Abhishek Jain, and Vinod Vaikuntanathan. 2015. Succinct garbling and indistinguishability obfuscation for RAM programs. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC’15). 429--437.
30. Ran Canetti, Huijia Lin, Stefano Tessaro, and Vinod Vaikuntanathan. 2015. Obfuscation of probabilistic circuits and applications. In Proceedings of the Theory of Cryptography Conference (TCC’15).
31. Ran Canetti, Guy N. Rothblum, and Mayank Varia. 2010. Obfuscation of hyperplane membership. In Proceedings of the 7th Theory of Cryptography Conference (TCC’10) (Lecture Notes in Computer Science), Daniele Micciancio (Ed.), Vol. 5978. Springer, 72--89.
32. Angelo De Caro, Vincenzo Iovino, Abhishek Jain, Adam O’Neill, Omer Paneth, and Giuseppe Persiano. 2013. On the achievability of simulation-based security for functional encryption, see Reference Canetti and Garay {28}, 519--535.
33. Stephen A. Cook and H. James Hoover. 1985. A depth-universal circuit. SIAM J. Comput. 14, 4 (1985), 833--839.
34. Uriel Feige and Adi Shamir. 1989. Zero knowledge proofs of knowledge in two rounds. In Proceedings of the Annual International Cryptology Conference (CRYPTO’89). 526--544.
35. Sanjam Garg, Craig Gentry, and Shai Halevi. 2013. Candidate multilinear maps from ideal lattices. In Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’13). 1--17.
36. Sanjam Garg, Craig Gentry, Shai Halevi, Amit Sahai, Mariana Raikova, and Brent Waters. 2013. Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS’13).
37. Sanjam Garg, Craig Gentry, Shai Halevi, and Mark Zhandry. 2016. Functional encryption without obfuscation. In Proceedings of the 13th International Theory of Cryptography Conference (TCC’16). 480--511.
38. Sanjam Garg, Omkant Pandey, and Akshayaram Srinivasan. 2016. Revisiting the cryptographic hardness of finding a Nash equilibrium. In Proceedings of the Annual International Cryptology Conference (CRYPTO’16).
39. Sanjam Garg, Omkant Pandey, Akshayaram Srinivasan, and Mark Zhandry. 2017. Breaking the sub-exponential barrier in obfustopia. In Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’17). 156--181.
40. Sanjam Garg and Akshayaram Srinivasan. 2016. Single-key to multi-key functional encryption with polynomial loss. In Proceedings of the 14th International Theory of Cryptography Conference (TCC’16). 419--442.
41. Craig Gentry, Allison B. Lewko, Amit Sahai, and Brent Waters. 2015. Indistinguishability obfuscation from the multilinear subgroup elimination assumption. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS’15).
42. Oded Goldreich. 2001. The Foundations of Cryptography—Volume 1, Basic Techniques. Cambridge University Press.
43. Oded Goldreich, Shafi Goldwasser, and Silvio Micali. 1986. How to construct random functions.J. ACM 33, 4 (1986), 792--807.
44. Shafi Goldwasser, S. Dov Gordon, Vipul Goyal, Abhishek Jain, Jonathan Katz, Feng-Hao Liu, Amit Sahai, Elaine Shi, and Hong-Sheng Zhou. 2014. Multi-input functional encryption. In Proceedings of the 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’14). 578--602.
45. Shafi Goldwasser and Yael Tauman Kalai. 2005. On the impossibility of obfuscation with auxiliary input. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS’05). IEEE Computer Society, 553--562.
46. Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich. 2013. Reusable garbled circuits and succinct functional encryption. In Proceedings of the Symposium on Theory of Computing Conference (STOC’13). 555--564.
47. Shafi Goldwasser and Guy N. Rothblum. 2007. On best-possible obfuscation. In Proceedings of the Theory of Cryptography Conference (TCC’07). 194--213.
48. Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. 2012. Functional encryption with bounded collusions via multi-party computation. In Proceedings of the Annual International Cryptology Conference (CRYPTO’12). 162--179.
49. Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. 2013. Attribute-based encryption for circuits. In Proceedings of the Symposium on Theory of Computing Conference (STOC’13). 545--554.
50. Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. 2015. Predicate encryption for circuits from LWE. IACR Cryptol. ePrint Arch. 2015 (2015), 29. Retrieved from http://eprint.iacr.org/2015/029.
51. Satoshi Hada. 2000. Zero-knowledge and code obfuscation. In Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT’00). 443--457.
52. Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. 1999. A pseudorandom generator from any one-way function. SIAM J. Comput. 28, 4 (1999), 1364--1396.
53. Dennis Hofheinz, John Malone-Lee, and Martijn Stam. 2007. Obfuscation for cryptographic purposes. In Proceedings of the 4th Theory of Cryptography Conference (TCC’07) (Lecture Notes in Computer Science), Salil P. Vadhan (Ed.), Vol. 4392. Springer, 214--232.
54. Susan Hohenberger, Guy N. Rothblum, Abhi Shelat, and Vinod Vaikuntanathan. 2011. Securely obfuscating re-encryption. J. Cryptol. 24, 4 (2011), 694--719.
55. Yuval Ishai and Eyal Kushilevitz. 2000. Randomizing polynomials: A new representation with applications to round-efficient secure computation. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS’00). IEEE Computer Society, 294--304.
56. Jonathan Katz, Amit Sahai, and Brent Waters. 2013. Predicate encryption supporting disjunctions, polynomial equations, and inner products. J. Cryptol. 26, 2 (2013), 191--224.
57. Aggelos Kiayias, Stavros Papadopoulos, Nikos Triandopoulos, and Thomas Zacharias. 2013. Delegatable pseudorandom functions and applications. In Proceedings of the ACM Conference on Computer and Communications Security (CCS’13), Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung (Eds.). ACM, 669--684.
58. Fuyuki Kitagawa, Ryo Nishimaki, and Keisuke Tanaka. 2017. Indistinguishability obfuscation for all circuits from secret-key functional encryption. IACR Cryptol. ePrint Arch. 2017 (2017), 361. Retrieved from http://eprint.iacr.org/2017/361.
59. Ilan Komargodski, Tal Moran, Moni Naor, Rafael Pass, Alon Rosen, and Eylon Yogev. 2014. One-way functions and (im)perfect obfuscation. In Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS’14). IEEE Computer Society, 374--383.
60. Venkata Koppula, Allison Bishop Lewko, and Brent Waters. 2015. Indistinguishability obfuscation for turing machines with unbounded memory. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC’15). 419--428.
61. Baiyu Li and Daniele Micciancio. 2016. Compactness vs. collusion resistance in functional encryption. In Proceedings of the 14th International Theory of Cryptography Conference (TCC’16). 443--468.
62. Huijia Lin. 2016. Indistinguishability obfuscation from constant-degree graded encoding schemes. In Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’16). 28--57.
63. Huijia Lin. 2017. Indistinguishability obfuscation from SXDH on 5-linear maps and locality-5 PRGs. In Proceedings of the 37th Annual International Cryptology Conference (CRYPTO’17). 599--629.
64. Huijia Lin, Rafael Pass, Karn Seth, and Sidharth Telang. 2016. Indistinguishability obfuscation with non-trivial efficiency. In Proceedings of the 19th IACR International Conference on Practice and Theory in Public-Key Cryptography (PKC’16). 447--462.
65. Huijia Lin, Rafael Pass, Karn Seth, and Sidharth Telang. 2016. Output-compressing randomized encodings and applications. In Proceedings of the 13th International Theory of Cryptography Conference (TCC’16). 96--124.
66. Huijia Lin and Stefano Tessaro. 2017. Indistinguishability obfuscation from trilinear maps and block-wise local PRGs. In Proceedings of the 37th Annual International Cryptology Conference (CRYPTO’17). 630--660.
67. Huijia Lin and Vinod Vaikuntanathan. 2016. Indistinguishability obfuscation from DDH-like assumptions on constant-degree graded encodings. In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS’16). 11--20.
68. Qipeng Liu and Mark Zhandry. 2017. Decomposable obfuscation: A framework for building applications of obfuscation from polynomial hardness. In Proceedings of the 15th International Conference on Theory of Cryptography (TCC’17). 138--169.
69. Ben Lynn, Manoj Prabhakaran, and Amit Sahai. 2004. Positive results and techniques for obfuscation. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’04) (Lecture Notes in Computer Science), Christian Cachin and Jan Camenisch (Eds.), Vol. 3027. Springer, 20--39.
70. Adam O’Neill. 2010. Definitional issues in functional encryption. Cryptology ePrint Archive, Report 2010/556. (2010).
71. Rafael Pass, Karn Seth, and Sidharth Telang. 2014. Indistinguishability obfuscation from semantically secure multilinear encodings. In Proceedings of the 34th Annual Cryptology Conference (CRYPTO’14) (Lecture Notes in Computer Science), Juan A. Garay and Rosario Gennaro (Eds.), Vol. 8616. Springer, 500--517.
72. Amit Sahai and Hakan Seyalioglu. 2010. Worry-free encryption: Functional encryption with public keys. In Proceedings of the ACM Conference on Computer and Communications Security (CCS’10). 463--472.
73. Amit Sahai and Brent Waters. 2005. Fuzzy identity-based encryption. In Proceedings of the 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’05) (Lecture Notes in Computer Science), Ronald Cramer (Ed.), Vol. 3494. Springer, 457--473.
74. Amit Sahai and Brent Waters. 2014. How to use indistinguishability obfuscation: Deniable encryption, and more. In Proceedings of the Symposium on Theory of Computing (STOC’14), David B. Shmoys (Ed.). ACM, 475--484.
75. Leslie G. Valiant. 1976. Universal circuits (preliminary report). In Proceedings of the 8th Annual ACM Symposium on Theory of Computing (STOC’76). 196--203.
76. Hoeteck Wee. 2005. On obfuscating point functions. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC’05), Harold N. Gabow and Ronald Fagin (Eds.). ACM, 523--532.
77. Andrew Chi-Chih Yao. 1986. How to generate and exchange secrets (extended abstract). In Proceedings of the 27th Annual Symposium on Foundations of Computer Science (FOCS’86). IEEE Computer Society, 162--167.
78. Joe Zimmerman. 2015. How to obfuscate programs directly. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’15).

Index Terms

• Security and privacy

  • Cryptography

    • Mathematical foundations of cryptography