UC Santa Barbara

Zero-Knowledge Protocols and Witness Encryption are usually defined for NP relations. I show that they can be extended to handle promiseMA relations. For witness encryption, this simply results in polynomially-longer instances and witnesses. For zero-knowledge protocols, this may require one additional round of interaction, since the prover needs to receive an allegedly random string from the verifier, but the structure of the protocol does not otherwise change, and soundness holds even if the prover chooses its instance after seeing that allegedly random string.

It is known that efficient virtual black-box obfuscation of functions is impos- sible, but there are candidate constructions of indistinguishability obfuscation, and one can trivially build witness encryption from indistinguishability obfusca- tion. I show that if witness encryption exists, then there is no virtual black-box obfuscation of distributions against auxiliary input.