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.
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.
Comments
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.
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.