Hacker News Reader

Comment by jere | Hacker News Reader

>They adopt a different definition of obfuscation, called indistinguishability obfuscation. The criterion for success is that an adversary who is given obfuscated versions of two distinct but equivalent programs—they both compute the same function—can’t tell which is which.

I don't follow this part. Obviously, if you have two distinct programs, they are different and you could arbitrarily label one A and the other B. And even if you couldn't do that, so what? Anyone care to explain?

View on HN

You give me two equivalent programs, A and B. I give you obfuscated versions of both, lets call them C and D. You can't tell whether I produced C from A and D from B, or C from B and D from A.

This property prevents certain class of cracks, making it harder to pirate software.

Consider the following example: a vendor provides a free demo and a paid version of the same program. Functionality is the same (`computes the same function'), the paid full version uses a good O(log(m) + log(n)) algorithm while the free demo is purposefully encumbered with a bad O(m * n) algorithm -- in hopes of making you pay for heavy use of the program.

Now the property means you can't really trace which exactly part of the program encodes the key algorithm, thus you can't really patch the demo version to the full version.

Yeah, I don't follow this either. If they are equivalent programs- they both compute the same function- then what does it matter which is which? Also how would this apply

Or obfuscation could help in producing "crippleware"—try-out versions of a program that have certain functions disabled.

Because then they wouldn't be computing the same thing, would they?

> then what does it matter which is which?

because implementation details matter, like the given example, demonstrating the ability to factor large numbers, without giving away the algorithm that does so.

In this case, we've defined a function, PrimeFactor(x), which returns the prime factorization of x.

you can write a naive program that computes PrimeFactor(x) by brute force. it will be slow but it will work. let's call this ProgramA.

let's say I write a magic, genius program that computes PrimeFactor(x) in constant time. This is ProgramB.

Given ProgramA, and ProgramB, you can correctly assert that ProgramA(x) == ProgramB(x) for all x.

If you ran A and B through a indistinguishability obfuscator to obtain ObfuscatedProgramC and ObfuscatedProgramD, the assertion that C(x) == D(x) holds, but you'd have no way of telling whether C comes from A or B (apart from runtime, which is ignored here)

By the same token, you couldn't tell if C and D both came from A, or both came from B, or any other possible program that correctly computes PrimeFactor(x).

so in theory, an indistinguishability obfuscator allows someone to know what a program computes, but not how it computes it, and implementation can matter a great deal.

>you can write a naive program that computes PrimeFactor(x) by brute force. it will be slow but it will work. let's call this ProgramA.

Ah, that's a good way to think about it. Thanks!

How is that weaker (or any different) from the obfuscator that was proven to not exist? Namely, an obfuscator that preserves functionality and has the black box property.

I think the key point is the effienctly compute in the defintion. It seems that the black box property means C() and an oracle version of A() must be completely indistinguishable, including things like runtime and memory usage.

The weaker obfuscator has no guarantee about that.

I thought it meant two programs which compute the same thing but possibly using different algorithms. If they are indistinguishable then you can't infer from the improved algorithm anything you can't get from the old one.

Reply on news.ycombinator.com