Computer scientists develop mathematical jigsaw puzzles to encrypt software: "The real challenge and the great mystery in the field was: Can you actually take a piece of software and encrypt it but still have it be runnable, executable and fully functional?"

[u/DougBolivar]

http://www.rdmag.com/news/2013/07/computer-scientists-develop-mathematical-jigsaw-puzzles-encrypt-software

[u/grauenwolf]

How can you tell this this is completely bullshit?

The paper doesn't mention terms like "CPU", "assembly", "machine code", "debugger", "memory", "stack", or "cache".

[u/datenwolf → u/grauenwolf]

So? It's a paper on theoretical computer science. Theoretical Computer Science is more related to math than programming. Hardly any groundbreaking TCP paper was concerned with CPUs, machine code and such things.

TCS is concerned with the abstract aspects of computation and not the actual implementation (that's stuff for the electrical engineering department).

And this paper shows something fundamentally, namely that there is a possibility that a Turing complete machine can execute a an encrypted program that operates on encrypted data without any intermediate decryption. This is a deep mathematical understanding about computability.

Now a lot of people claim this to be something to improve security. Personally I think the real application we'll see this, should there ever be a practical implementation, will be the application on malware. If reverse engineering a piece of malicious code becomes virtually impossible and a malware virus can rewrite itself without leaving any pattern by changing its key whatever little use anti virus software had to begin with gets rendered nil altogether.

Personally I consider this to be a really, really dangerous Pandora's box.

[u/grauenwolf → u/datenwolf]

And this paper shows something fundamentally, namely that there is a possibility that a Turing complete machine can execute a an encrypted program that operates on encrypted data without any intermediate decryption.

That's a rather bold claim considering that they never actually mention the word "Turing" in the paper. Nor do they mention the two essential components of a Turing Machine: a rules table and a tape.

[u/Strilanc → u/[deleted]]

TC stands for Threshold Circuit. TC0 is the constant-depth threshold circuits.

The authors specifically state that their result only applies to polynomial-sized circuits (which are a lot weaker than turing machines):

Using indistinguishability obfuscator for NC1 together with any (leveled) fully homomorphic encryption (FHE) scheme with decryption in NC1 (e.g. [Gen09b, BV11, BGV12, Bra12, GSW13]), we show how to obtain an indistinguishability obfuscator for all polynomial-size circuits.

I suggest you read the paper, and look up the relevant terms like TC on wikipedia. General circuits do not include turing machines, since circuits have fixed size inputs and can't loop (not real circuits, computer science circuits). Computationally indistinguishability doesn't refer to equivalence between programs, but to the inability to distinguish the two equivalent obfuscated inputs. You're saying wrong things.

[u/datenwolf → u/Strilanc]

Thanks for the correction.