We study several problems in the intersection of cryptography and complexity theory based on the following high-level thesis.
1) Obfuscation can serve as a general-purpose *worst-case to average-case reduction*, reducing the existence of various forms of cryptography to corresponding worst-case assumptions.
2) We can therefore hope to overcome ...
more >>>
We obtain new explicit pseudorandom generators for several computational models involving groups. Our main results are as follows:
1. We consider read-once group-products over a finite group $G$, i.e., tests of the form $\prod_{i=1}^n g_{i}^{x_{i}}$ where $g_{i}\in G$, a special case of read-once permutation branching programs. We give generators with ... more >>>
We study connections between two fundamental questions from computer science theory. (1) Is witness encryption in the sense of Garg et al. (2013) possible for NP? That is, given an instance $x$ of an NP-complete language $L$, can one encrypt a secret message with security contingent on the ability to ... more >>>