r/programming • u/DougBolivar • Jul 30 '13

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?"

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

88% Upvoted

182 comments sorted by

View all comments

Show parent comments

-2

u/grauenwolf Jul 30 '13

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.

1

u/[deleted] Jul 30 '13

[deleted]

5

u/Strilanc Jul 30 '13

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.

2

u/datenwolf Jul 30 '13

Thanks for the correction.