There is something I don't get it there though. Wouldn't you, with a debugger for instance, be able to see the program as it would have to deobfuscate itself for the processor to understand it ?
That presumes that being able to "see the program" reveals anything about the cipher or its key. In the white-box crypto model, it doesn't; the source code is itself "encrypted", so that its basic operations are visible but the precise sequence of operations it will taken given a specific input are Hard to determine.
Interesting possibility in white-box model is ability to take something invertible (eg. block cipher) and instantiate it in a way that cannot be inverted. That would allow for building fixed key signature mechanism with essentially arbitrary signature size equal to security level.
Another question is whether usable (ie. reasonable code and data sizes) and secure (with "hard" in the cryptographic sense, not in the sense of non-obvious) white-box cryptography is actually possible.
But this can't work without blackbox TPM chip that are not under your control anymore...
Thus for this to work you have to give up general purpose computing?
That's a very conventional method of obfuscation. What the paper proposes is that the program would do a series of random actions which would add up to the original program + a lot of noise.
I don't claim to understand the details at all, but I would at least imagine the obfuscated program to be so complex and with so much indirectness and "virtual-machine"-ness that any kind of single stepping would yield an absolutely incomprehensible state at every point until termination.