F-obf — Obfuscation

F-obf (Obfuscation) is part of Public-Key Primitives, Key Exchange, Messaging in the UC functionality encyclopedia. Status: open — no accepted UC formulation exists yet.

Neither cited paper prints an obfuscation functionality, and the reason is the same one that makes F-SNARK a different object from its title: an ideal functionality has no program whose intelligibility it could bound. Obfuscation is a property of a compiler from programs to programs, stated by comparing what an adversary learns from the output program against what it learns from oracle access to the input program. A functionality that evaluated the program would be an oracle already, and would therefore say nothing at all.

The former title claimed more than the sources support. It read “Obfuscation, split VBB, iO”. Neither paper below uses the phrase “split VBB”; it appears nowhere in either, checked. Indistinguishability obfuscation appears in the second paper — as an assumption it builds on, not as an object it defines. Retitled to the one word both papers are about.

Why there is no box

Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan and Yang, 2001 is a pre-UC, complexity-theoretic paper: the word “functionality” occurs in it only in the sense of “\(O(P)\) computes the same function as \(P\)”, one of the two properties an obfuscator must have. Its formalization is a game between an adversary with the obfuscated program and a simulator with oracle access — “anything that can be efficiently computed from \(O(P)\) can be efficiently computed given oracle access to \(P\)” — and its result is that even “under very weak formalizations of the above intuition, obfuscation is impossible”. There is no ideal-process comparison, no environment and no adversary slot; the paper predates none of that, but it is not written in those terms and nothing in it is a functionality.

And the impossibility is the load-bearing part for this page. If general virtual-black-box obfuscation cannot exist, then a functionality asserting it would be unrealizable by construction — which does not by itself forbid writing one down (this encyclopedia carries several unrealizable setup functionalities), but it does explain why nobody has: the interesting statements about obfuscation are about which obfuscators exist under which relaxation, and a single box cannot be parameterized over relaxations of its own security notion.

Canetti, Goldwasser and Poburinnaya, 2015 prints ideal functionalities, and none of them is about obfuscation. What it defines is a transformation on functionalities: it calls a functionality incoercible when, on being asked by the ideal-model adversary for a party’s internal information, it “first asks the environment” whether to hand over the real input or a fake one, and returns whichever the environment names. Indistinguishability obfuscation is one of the assumptions its protocol rests on — alongside one-way functions and augmented non-committing encryption — and it is used, never idealized. That transformation is F-incoerc’s subject, not this page’s.

A comparison worth making. F-wrap, the tamper-proof hardware token, is the closest thing in this encyclopedia to an idealized obfuscation: a party loads a program into a box and everyone else may only query it. That is what obfuscation would buy if it existed, and it is exactly why the token is a setup assumption here rather than something a protocol realizes. Anyone who wants “an obfuscated program” in this framework is looking for that page.

What each citation yielded

  • Barak et al. 2001 — read as ePrint 2001/069, revision 20010815:163452 (its only posting, PostScript only; the PDF read here was produced with Ghostscript, 43 pages). Prints no ideal functionality. The seven authors are named above; the stub cited it as “Barak et al.”
  • Canetti, Goldwasser and Poburinnaya 2015 — read as ePrint 2014/845, revision 20160223:012320, the newer of two postings (30 pages). Prints incoercible ideal functionalities, in its §1 and §2; prints no obfuscation functionality.

What would resolve this

  1. Find a paper that prints one. A UC-framework paper defining an obfuscation functionality — with a Load interface taking a program and an Eval interface answering queries on it. It would be very close to F-wrap, and the honest version of this page’s question is whether it would be anything else: if the only difference from a hardware token is who is trusted, then obfuscation has no functionality of its own and the slot should record that rather than duplicate the token.
  2. Retire the slot. Obfuscation may simply be a primitive whose security notion has no ideal-world counterpart, in the way succinctness has none — the argument on F-SNARK is the same shape, and that page resolved it by carrying a different box that its citations did print. There is no such alternative here: neither citation prints anything this page could carry.

Until one of those happens, this page’s definition field reads No canonical definition, which scripts/uc_status.py treats as a claim a human may write and a script may not.

Formal artifacts

No machine-checked formalization yet, and none is possible before there is a definition to formalize.

References:

  • Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang. On the (im)possibility of obfuscating programs. In Advances in Cryptology – CRYPTO 2001, 2001. Read at revision 20010815:163452, its only posting, which is PostScript-only. Prints no ideal functionality; its “functionality” condition is the requirement that the obfuscated program compute the same function, and its main result is that obfuscation is impossible even under very weak formalizations of the virtual-black-box property.
  • Canetti, Goldwasser, and Poburinnaya. Adaptively secure two-party computation from indistinguishability obfuscation. In 12th Theory of Cryptography Conference (TCC), Part II, pages 557–585, 2015. Read at revision 20160223:012320, the newer of two postings. Prints incoercible ideal functionalities — see F-incoerc — and uses indistinguishability obfuscation with sub-exponential security as an assumption rather than defining a functionality for it.