COA-Secure Obfuscation and Applications

We put forth a new paradigm for program obfuscation, where obfuscated programs are endowed with proofs of ``well-formedness.'' In addition to asserting existence of an underlying plaintext program with an attested structure and functionality, these proofs also prevent mauling attacks, whereby an adversary surreptitiously creates an obfuscated program based on secrets which are embedded in a given obfuscated program.
We call this new guarantee Chosen Obfuscation Attack (COA) security.

We define and construct general-purpose COA-secure Probabilistic Indistinguishability Obfuscators for circuits, assuming sub-exponential IO for circuits and CCA commitments. To demonstrate the power of the new notion, we use it to realize, in the plain model:

• Structural Watermarking, which is a new form of software watermarking that provides significantly broader protection than current schemes and features a keyless, public verification process.
• Completely CCA encryption, which is a strengthening of completely non-malleable encryption.

We also show, based on the same assumptions, a generic method for enhancing any obfuscation mechanism that guarantees any semantic-style form of hiding to one that provides also COA security.