3 ms·
This is confusing: >For decades, computer scientists wondered if there is any secure, all-encompassing way to obfuscate computer programs, allowing people to u
by nottorp 6y ago
This is confusing:
>For decades, computer scientists wondered if there is any secure, all-encompassing way to obfuscate computer programs, allowing people to use them without figuring out their internal secrets.
Obfuscate executable code? Somehow I don't think the original paper is talking about that.
<skims through the beginning of the paper>
They are?
But... how do you execute it then?
- deleted 6y ago[deleted]
- bawolff 6y ago> Obfuscate executable code? Somehow I don't think the original paper is talking about that. Why not? Technically its talking about polynomial sized circuits, but that is roughly the same thing. To quote the paper, the property they are looking for: "(T, γ)-Indistinguishability: For every two ensembles {C_0,λ} {C_1,λ} of polynomial-sized circuits that have the same size, input length, and output length, and are functionally equivalent, that is, ∀λ, C_0,λ(x) = C_1,λ(x) for every input x, the following distributions are (T, γ)- indistinguishable: {iO(1^λ, C_0,λ)} {iO(1^λ, C_1,λ)}"
- bawolff 6y ago> But... how do you execute it then? You still end up with executable code - i think the key thing is you get it to a form where you can't tell the difference between your function (after obfuscation) and any other function that gives the same output for same input (after obfuscation). So you could still try giving it every possible input, to figure out what it does, but if it takes at least a couple 64 bit integers you're going to be spending the rest of your life doing that.
- sillysaurusx 6y agoWelcome to the joys of fully homomorphic encryption. Enjoy your stay. And wonder why more people aren’t talking about it. Because you can execute it!
- MauranKilom 6y agoIn short: Math. To elaborate: Sure, your computer has to know all the numbers and instructions it executes. But that doesn't require your computer or you to understand what those numbers or instructions mean. The meaning can be guarded by encryption. For example, if you are given a ROT13 encrypted text, you could uppercase all the letters without understanding the message. You perform an operation on the ciphertext without being able to decipher it, and the result (once decrypted) is exactly the same as if the operation had been applied to the plaintext. This is what fully homomorphic encryption (FHE) is about. Going further, you can also have the effect of the instructions themselves be "hidden" by encryption. As a very simple example, imagine a programming language where all you can do is multiply numbers with constants (and there are different "instructions" for multiplying with different numbers). Your unencrypted program might be "multiply by 3, then multiply by 5, then multiply by 2". In encrypted form, this might become "multiply by 21, then multiply by 35, then multiply by 14" - that is, every factor is itself multiplied by seven, leading to different instructions. Someone running this encrypted program on (possibly homomorphically encrypted) data will not be able to figure out your original program (unless they know the "key" - that every factor was multiplied by seven). But when you get back the result, all you need to do is divide it by 7x7x7 to get back the output of the original program. And all the "difficult" computations (the actual instructions) have been performed on somebody else's machine without them knowing your original program (or your plaintext data, if the entire thing is also fully homomorphic). I hope this example somewhat illustrates the concept (even though it is of course flawed and entirely trivial). Just imagine significantly more and better math instead of the simple operations (e.g. multiplication as only instruction, "decryption" by division etc.) used above. And of course, you can't just slap FHE on top independently, it needs to be built into the system. But the idea is the same.
- nottorp 6y agoLooks smart theoretically. Practically I suppose it would be useful in a bunch of corner cases where people are extra paranoid about their IP. Or at least you could make money selling this to people who are extra paranoid about the IP. For normal utility programs, I don't know. I mean, the data has to be unencrypted at some point for a human to make sense of it. What use is a fully obfuscated email client if you can't read your mail with it?
- deleted 6y ago[deleted]