For which class of circuits does the Virtual black box(VBB) obfuscator exists? If so Why? What are the attempts/further developments made in this topic?


1 Answer 1


While the question was different, you can extract the answer from my answer to this question. Summing up:

  • Under LWE, we have (distributional) VBB obfuscation for conjunctions
  • Under multilinear maps (the flavor of which can possibly be constructed from iO, which itself now exists under relatively standard assumptions), we have VBB for evasive low-degree polynomials modulo a prime
  • Under entropic DDH, we have (distributional) VBB for pattern matching and hyperplane membership
  • Under exponentially strong OWFs (or OWP), we have VBB for point functions

On the other hand, via the classical result of Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang, whenever the class of functions contains a PRF, you cannot have VBB obfuscation for it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.