[talks] Qipeng Liu will present his general exam on Friday, May 12, 2017 at 1pm in CS 301.
ngotsis at CS.Princeton.EDU
Fri May 5 13:18:00 EDT 2017
Qipeng Liu will present his general exam on Friday, May 12, 2017 at 1pm in CS 301. The members of his committee are: Mark Zhandry (Adviser), Zeev Dvir, and Ran Raz.
Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below.
Program obfuscation — scrambling code to hide embedded secrets — has emerged as a powerful tool that can solve a variety of cryptographic tasks. Unfortunately, there is some evidence that the precise notion of obfuscation used by cryptographers — called indistinguishability obfuscation (iO) — requires either exponentially many different cryptographic assumptions or (sub)exponentially hard assumptions. Indeed, all known ways of building obfuscation suffer one of these two limitations. As such, any application built from iO suffers from these limitations as well. However, for most applications, such limitations do not appear to be inherent to the application, just the approach using iO. Indeed, several recent works have shown how to base applications of iO instead on functional encryption (FE), which can in turn be based on the polynomial hardness of just a few assumptions. However, these constructions are quite complicated and recycle a lot of similar techniques. In this work, we unify the results of previous works in the form of a weakened notion of obfuscation, called Exploding iO. We show (1) how to build exploding iO from functional encryption, and (2) how to build a variety of applications from exploding iO, including all of the applications already known from FE. The construction in (1) hides most of the difficult techniques in the prior work, whereas the constructions in (2) are much closer to the comparatively simple constructions from iO. As such, exploding iO represents a convenient new platform for obtaining more applications from polynomial hardness.
1. Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S. and Yang, K., 2001, August. On the (im) possibility of obfuscating programs. In Annual International Cryptology Conference (pp. 1-18). Springer Berlin Heidelberg.
2. Garg, S., Gentry, C., Sahai, A. and Waters, B., 2013, June. Witness encryption and its applications. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing (pp. 467-476). ACM.
3. Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A. and Waters, B., 2016. Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM Journal on Computing, 45(3), pp.882-929.
4. Sahai, A. and Waters, B., 2014, May. How to use indistinguishability obfuscation: deniable encryption, and more. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (pp. 475-484). ACM.
5. Ananth, P. and Jain, A., 2015, August. Indistinguishability obfuscation from compact functional encryption. In Annual Cryptology Conference (pp. 308-326). Springer Berlin Heidelberg.
6. Bitansky, N. and Vaikuntanathan, V., 2015, October. Indistinguishability obfuscation from functional encryption. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on (pp. 171-190). IEEE.
7. Garg, S., Pandey, O. and Srinivasan, A., 2016, August. Revisiting the cryptographic hardness of finding a nash equilibrium. In Annual Cryptology Conference (pp. 579-604). Springer Berlin Heidelberg.
8. Garg, S., Pandey, O., Srinivasan, A. and Zhandry, M., 2016. Breaking the Sub-Exponential Barrier in Obfustopia. IACR Cryptology ePrint Archive, 2016, p.102.
9. Garg, S. and Srinivasan, A., 2016, November. Single-key to multi-key functional encryption with polynomial loss. In Theory of Cryptography Conference (pp. 419-442). Springer Berlin Heidelberg.
10. Textbook: Introduction to Modern Cryptography (2nd Edition) by Jonathan Katz and Yehuda Lindell.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the talks