9 ms·

Indistinguishability Obfuscation from Well-Founded Assumptions

197 points by theafh 6y ago

sillysaurusx 6y ago
Fully homomorphic encryption?! Reads article Yup! Gosh, I can't wait for it to become remotely practical. It's been a few years -- wow, almost a decade -- but I remember a paper that claimed to prove that "no fully homomorphic program can be written such that the secret key was guarded in all cases," i.e. it's theoretically possible to trick a FHE program into giving up its own key, unless your program is basically trivial. It was one of those papers that you run across, then never see again, and wistfully wish you'd saved a reference to. Tantalizing idea, if true, but probably not true. EDIT: I just went back to finish the article, and they linked to it: https://link.springer.com/chapter/10.1007/3-540-44647-8_1 https://link.springer.com/chapter/10.1007/3-540-44647-8_1 Welp. Looks like it was a good paper!
- hacknat 6y ago
  Reading the abstract of the "paper" (book) that you linked it looks like what they are attempting to prove is that there are classes of functions in which obfuscation is impossible. My guess is that iO could still be attempted by simply guarding against these certain classes (which may even be difficult to create in the real world). However, that book does look daunting. I am curious if the book hints at more potential problems than the abstract indicates.
  - sillysaurusx 6y ago
    Unlocked paper: https://moscow.sci-hub.se/2256/6ffcc08f6e40c37f84b5287edf9a57bb/barak2001.pdf https://moscow.sci-hub.se/2256/6ffcc08f6e40c37f84b5287edf9a5... I wish I had endless free time. It would be so, so fun to dive into this. Because you’re right — I got the sense that there were more potential problems than was previously appreciated. It would be fascinating to know exactly what problems there are, and whether they’re fundamental problems or “dodgeable.”
- bawolff 6y ago
  I haven't fully absorbed this, but isn't this kind of the opposite of FHE? In FHE you are hiding the input and output. Here you are hiding the function (or in the PHFE application the function and part of the input)
  - sillysaurusx 6y ago
    Hmm. I thought “fully homomorphic encryption” == “hiding the function,” not merely input and output. Have I been using that term incorrectly? It’s possible. If so, what’s the canonical acronym for “encrypting a function”?
    - feanaro 6y ago
      FHE is the ability to encrypt some data and give it to a machine, which is then able to perform sensible operations on it without decrypting it (and thus ever learning the plaintext). The term you are looking for is "obfuscation". Either black-box obfuscation (which was shown to be impossible) or the indistinguishability obfuscation, which is what the article talks about.
    - aruss 6y ago
      You can encrypt a function with FHE, but the applications of that are limited because the output is encrypted as well. We've had provably secure FHE since Gentry's 2009 paper. Obfuscation roughly means "encrypting a function." But here be dragons: since the adversary gets non-black-box access to the implementation of the function (a circuit), and can also learn as many (input, output = f(input)) pairs as they want, it becomes impossible to say that the adversary cannot learn anything else about f in the general case (intuitively, consider a higher-order function f: you could learn a lot about f by computing f(f)).
- KenoFischer 6y ago
  The article isn't about FHE, it's about iO. As you point out there's no reduction from FHE to iO, but there is one going the other way. Worth noting though that when Boaz et al wrote that paper, even FHE wasn't known to exist. As for the iO result, not sure whether you were saying you thought the result wasn't solid because of the Boaz paper, but my understanding from people in the field is that it's expected to hold up and of course Boaz is quoted in the article.
  - sillysaurusx 6y ago
    Can someone break down in simple terms what the difference is between FHE and iO? What can you do with FHE that you can’t do with iO? A concrete example would help tremendously. I always mentally substituted FHE with “the ability to encrypt a function such that no attacker can reverse engineer how that function was implemented,” i.e. “input go in, output go brr.” Crucially, in FHE this is true even if you yourself are the one executing the program and can observe everything the program is doing. Or... in whatever I thought FHE was.
    - KenoFischer 6y ago
      In FHE, you need some sort of key to decrypt the result. In obfuscation the result comes out clear text. General obfuscation is impossible, but iO gives you basically the best possible result which is "given any method of computing the same function (for some complexity parameter of the function in question) you will always be able learn at least as much from said method as from the obfuscated function" (in other words iO gives you a circuit that is as hard to reverse engineer as the hardest circuit of a given size that computes the same function, but it doesn't give you a guarantee on how hard that actually is).
      - sillysaurusx 6y ago
        Suppose I have a function which returns input + 42. I wish to obfuscate that function so that no one can determine how I arrived at the result, even if they themselves are executing the program. In simple terms, why is FHE different from iO? I’ve read your reply a few times, but I don’t understand the concrete distinction. What is the “best possible result” of input + 42 obfuscatabiliry? Note that I am using + 42 as a trivial example; please mentally substitute with “for example, a bunch of matrix operations to compute a super secret formula result.”
AdmiralAsshat 6y ago
Just in time for the DoJ and the EU to tell them to intentionally cripple it for law enforcement purposes.
r00fus 6y ago
Some of the use cases presented sound like they'd be perfect for DRM.
- eternalban 6y ago
  Here is a short list of the downsides. I’m sure there is more. Tech is always double edged, it seems. - present false source to claimed binary build of same. - allow for pervasive backdoors in binary blobs that resist scrutiny by security researchers
  - csunbird 6y ago
    I don't think that game developers/media companies/etc care about the two things that you have mentioned. All they want is un-crackable DRM.
    - kaszanka 6y ago
      I feel like I'm in way over my head here, but how is it even possible to have mathematically uncrackable DRM? Surely at the end it's going to come down to a comparison instruction (or a few thousand of them), no?
      - avmich 6y ago
        So you want to modify those instructions to crack DRM? Which of them? There is a lot of instructions (say, your few thousand) and even more combinations of instructions, you can't find another combination of instructions which would work.
        kaszanka 6y ago
        I guess my problem is that I don't see a fundamental difference between this approach and traditional obfuscators/packers/virtualizers/whatever. They can also bloat a simple comparison (for example) into many seemingly useless but interconnected instructions. I just don't understand how it's possible to make a DRM scheme that can't be cracked.
mabbo 6y ago
Nit: Hiding what the neck you're talking about doesn't make for better journalism. If you're going to spend 9 paragraphs talking about the controversy of whether such a thing is possible or not, dedicate at least 1 sentence at the start to explain it. Otherwise it's just confusing because as a reader, I have no idea why I should care or what's even worth caring about here. Recommendation to anyone who hasn't read the article yet: start with the part called "The Crown Jewel".
- ksd482 6y ago
  Not just Nit, but I think this is a major point. It is my biggest pet peeve and I immediately back off from articles written in such manner. If writers write good introduction paragraph, it gauges my interest and I am more likely to read. Otherwise, I don't read out of spite or protest.
- anonunivgrad 6y ago
  It’s because journalists have no clue what they’re talking about. This is true for all journalism but you only notice it when it’s about something you’re familiar with.
  - bawolff 6y ago
    If you are going to diss the journalist, you should back it up with specific examples.
    - anonunivgrad 6y ago
      I mean journalists in general.
    - adrianmonk 6y ago
      This particular journalist has qualifications that suggest she probably does know what she's talking about. From https://www.quantamagazine.org/authors/erica-klarreich/ https://www.quantamagazine.org/authors/erica-klarreich/: > About the author > Erica Klarreich has been writing about mathematics and science for more than 15 years. She has a doctorate in mathematics from Stony Brook University and is a graduate of the Science Communication Program at the University of California, Santa Cruz.
beatle_sauce 6y ago
Is this basically the learning parity with noise problem, but instead of a fixed size vector, the noisy output is generated in by a PRNG with a pre-determined secret seed? How can this be used for authentication or encryption?
isaacimagine 6y ago
The important point here is that iO, once fully realized, can be used to derive other cryptographic primitives. Fully homomorphic encryption has been doing the rounds for a while now, but it's too slow for practical use - I wonder if this will change that.
some_furry 6y ago
> 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. As someone who works in cryptography, this isn't "The Crown Jewel" of Cryptography. Cryptography to me is about helping queer people live their best life even in countries where they're hated. Cryptography to me is about providing assurance that the software you're running was produced by the people you thought produced it, and that the built binary is reproducible from the source code, which technical people can also inspect to assert the absence of backdoors. Obfuscation and copy-protection are non-goals for me. Fully homomorphic encryption has uses in machine learning and cloud services, but I find them at odds with the goals I care about.
- bawolff 6y ago
  Arguably aren't those security engineering goals more than cryptography goals?
  - some_furry 6y ago
    I'm really not interested in splitting hairs over taxonomy. Real-world cryptography and security engineering intersect a lot.
    - bawolff 6y ago
      i would call both of those the same thing, and neither of them are cryptography.
      - some_furry 6y ago
        Is your argument "real-world cryptography isn't cryptography", or am I misunderstanding? EDIT: I can't reply due to rate-limiting, so here's my reply to your reply below: ----- > My argument is "real world cryptography" is a euphamism for security engineering for people who want to sound more badass. It's not a euphemism. Take a look at the accepted papers at the aptly named Real World Cryptography symposiums: https://rwc.iacr.org/2020/program.html https://rwc.iacr.org/2020/program.html Breaks on OCB2. Lattice attacks on TPMs. MPC research. Privacy-preserving telemetry. I'll accept that you may personally have only seen security engineering work under the guise of "real-world cryptography", but to call it a euphemism is erroneous. ----- > Well if someone wrote an article about the Poincaré conjecture calling it the "crown jewel" of math, and someone else said "actually I consider the primary goal of math to be in helping build low-cost housing and other practical issues," then they're talking about two different things. Both are math, but to say that the Poincaré conjecture isn't important to math because you use math primarily for different things is misleading. All of the proposals for homomorphic encryption I've seen to date (which, for transparency, were mostly in the realm of encrypted databases) don't provide any protection against chosen-ciphertext attacks. If [F]HE isn't IND-CCA2 secure, which is the minimum bar for encryption that should be used outside of academic settings, then calling it the crown jewel only serves to hype up a technology that will fail to protect users.
karmakaze 6y ago
I'm no crypto expert and trying to follow along, but can't make this leap: > But iO is stronger than it sounds. For example, suppose you have a program that carries out some task related to your bank account, but the program contains your unencrypted password, making you vulnerable to anyone who gets hold of the program. Then — as long as there is some program out there that could perform the same task while keeping your password hidden — an indistinguishability obfuscator will be strong enough to successfully mask the password. After all, if it didn’t, then if you put both programs through the obfuscator, you’d be able to tell which obfuscated version came from your original program. Why does existence of another mask the secret? Even if you couldn't distinguish the programs, couldn't you just try both possible secrets?
- MauranKilom 6y ago
  Suppose there exist two programs that do the same task, with the following properties: - Knowing program A allows an attacker to recover your password. - Program B does not contain any information about your password. Eve knows that these programs exist and that they have these properties. Eve is now given two obfuscated programs O1 and O2. They were produced by applying iO to A and B, but Eve knows neither A, B nor how O1 and O2 map to O(A) and O(B). If it were possible for Eve to somehow obtain your password from, say (without loss of generality), O1 in any way, then Eve could deduce that O1 must be O(A). It could not be O(B) because neither O nor B contain information about your password. Since we assert that indistinguishable obfuscation makes it impossible to draw this kind of conclusion, it must be impossible to obtain your password from O(A) if B exists.
  - laszlokorte 6y ago
    I know nothing about the whole topic but could you explain: Why does any of those programs contain the password anyway if it is not needed for achieving the goal? If it is not needed, flow analysis, tree shaking and const evaluation could get rid of it. If it is needed, how would the program not containing it achieve the goal?
    - 6y ago
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 ago
  Welcome 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 ago
  In 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.
kemonocode 6y ago
@dang, it may be good to de-editorialize the title of this article. Best to simply say that indistinguishability obfuscation has been achieved.
- gus_massa 6y ago
  He usually prefer the subtitle: A cryptographic master tool called indistinguishability obfuscation has for years seemed too good to be true. Three researchers have figured out that it can work. Reduced to 80 characters it is: 12345678901234567890123456789012345678901234567890123456789012345678901234567890 Three researchers have figured out how indistinguishability obfuscation can work
- Ar-Curunir 6y ago
  The current title ("iO from Well-Founded Assumptions") is the title of the paper.
  - kemonocode 6y ago
    Yeah, that's much better now- definitively wasn't the case when it was submitted though!
    - gus_massa 6y ago
      I remember that the original title was the title of the press article "Computer Scientists Achieve ‘Crown Jewel’ of Cryptography". Sometimes the mods change them.
RcouF1uZ4gsC 6y ago
> Then — as long as there is some program out there that could perform the same task while keeping your password hidden — an indistinguishability obfuscator will be strong enough to successfully mask the password. I wonder if this will be the Achilles heel. If there were a way to perform a task without needing a secret, you would not be using homomorphic encryption. You could just do regular computation since there is no secret. However, if the only way to perform the computation is with the secret, then Indistinguishability Obsfuscation won't help you. To me it seems that iO is useful only for computations that didn't need homomorphic encryption in the first place, because they already had a way to do the computation without the secret.
- Ar-Curunir 6y ago
  There's been immense applications of iO in crypto already, constructing things we didn't know how to construct from the plain assumptions. This includes primitives which seem, at the first glance, to not have a "secret-less" equivalent.
anonymousisme 6y ago
I can see the malware/ransomware business really wanting this. It would make it impossible to circumvent or decrypt their warez.
- bawolff 6y ago
  Its already impossible if they implement (plain ole' public key) encryption properly
gumby 6y ago
Doesn't seem like they deal with the 10^6 X slowdowns you encounter with HE. Seems inherent to all the obfuscating computation.
no_identd 6y ago
The IAS about an hour ago uploaded Huijia (Rachel) Lin's talk on this: https://youtu.be/oBhQ58ntjdI https://youtu.be/oBhQ58ntjdI
- no_identd 6y ago
  Older (2 weeks) video series on this topic: • https://www.youtube.com/watch?v=v2RR_c5hn1E https://www.youtube.com/watch?v=v2RR_c5hn1E • https://www.youtube.com/watch?v=Al7Z53C4OQI https://www.youtube.com/watch?v=Al7Z53C4OQI • https://www.youtube.com/watch?v=8_0Rf0J8p3w https://www.youtube.com/watch?v=8_0Rf0J8p3w

197 points by theafh 6y ago

Fully homomorphic encryption?! Reads article Yup! Gosh, I can't wait for it to become remotely practical. It's been a few years -- wow, almost a decade -- but I remember a paper that claimed to prove that "no fully homomorphic program can be written such that the secret key was guarded in all cases," i.e. it's theoretically possible to trick a FHE program into giving up its own key, unless your program is basically trivial. It was one of those papers that you run across, then never see again, and wistfully wish you'd saved a reference to. Tantalizing idea, if true, but probably not true. EDIT: I just went back to finish the article, and they linked to it: https://link.springer.com/chapter/10.1007/3-540-44647-8_1 https://link.springer.com/chapter/10.1007/3-540-44647-8_1 Welp. Looks like it was a good paper!

hacknat 6y ago
Reading the abstract of the "paper" (book) that you linked it looks like what they are attempting to prove is that there are classes of functions in which obfuscation is impossible. My guess is that iO could still be attempted by simply guarding against these certain classes (which may even be difficult to create in the real world). However, that book does look daunting. I am curious if the book hints at more potential problems than the abstract indicates.
- sillysaurusx 6y ago
  Unlocked paper: https://moscow.sci-hub.se/2256/6ffcc08f6e40c37f84b5287edf9a57bb/barak2001.pdf https://moscow.sci-hub.se/2256/6ffcc08f6e40c37f84b5287edf9a5... I wish I had endless free time. It would be so, so fun to dive into this. Because you’re right — I got the sense that there were more potential problems than was previously appreciated. It would be fascinating to know exactly what problems there are, and whether they’re fundamental problems or “dodgeable.”
bawolff 6y ago
I haven't fully absorbed this, but isn't this kind of the opposite of FHE? In FHE you are hiding the input and output. Here you are hiding the function (or in the PHFE application the function and part of the input)
- sillysaurusx 6y ago
  Hmm. I thought “fully homomorphic encryption” == “hiding the function,” not merely input and output. Have I been using that term incorrectly? It’s possible. If so, what’s the canonical acronym for “encrypting a function”?
  - feanaro 6y ago
    FHE is the ability to encrypt some data and give it to a machine, which is then able to perform sensible operations on it without decrypting it (and thus ever learning the plaintext). The term you are looking for is "obfuscation". Either black-box obfuscation (which was shown to be impossible) or the indistinguishability obfuscation, which is what the article talks about.
  - aruss 6y ago
    You can encrypt a function with FHE, but the applications of that are limited because the output is encrypted as well. We've had provably secure FHE since Gentry's 2009 paper. Obfuscation roughly means "encrypting a function." But here be dragons: since the adversary gets non-black-box access to the implementation of the function (a circuit), and can also learn as many (input, output = f(input)) pairs as they want, it becomes impossible to say that the adversary cannot learn anything else about f in the general case (intuitively, consider a higher-order function f: you could learn a lot about f by computing f(f)).
KenoFischer 6y ago
The article isn't about FHE, it's about iO. As you point out there's no reduction from FHE to iO, but there is one going the other way. Worth noting though that when Boaz et al wrote that paper, even FHE wasn't known to exist. As for the iO result, not sure whether you were saying you thought the result wasn't solid because of the Boaz paper, but my understanding from people in the field is that it's expected to hold up and of course Boaz is quoted in the article.
- sillysaurusx 6y ago
  Can someone break down in simple terms what the difference is between FHE and iO? What can you do with FHE that you can’t do with iO? A concrete example would help tremendously. I always mentally substituted FHE with “the ability to encrypt a function such that no attacker can reverse engineer how that function was implemented,” i.e. “input go in, output go brr.” Crucially, in FHE this is true even if you yourself are the one executing the program and can observe everything the program is doing. Or... in whatever I thought FHE was.
  - KenoFischer 6y ago
    In FHE, you need some sort of key to decrypt the result. In obfuscation the result comes out clear text. General obfuscation is impossible, but iO gives you basically the best possible result which is "given any method of computing the same function (for some complexity parameter of the function in question) you will always be able learn at least as much from said method as from the obfuscated function" (in other words iO gives you a circuit that is as hard to reverse engineer as the hardest circuit of a given size that computes the same function, but it doesn't give you a guarantee on how hard that actually is).
    - sillysaurusx 6y ago
      Suppose I have a function which returns input + 42. I wish to obfuscate that function so that no one can determine how I arrived at the result, even if they themselves are executing the program. In simple terms, why is FHE different from iO? I’ve read your reply a few times, but I don’t understand the concrete distinction. What is the “best possible result” of input + 42 obfuscatabiliry? Note that I am using + 42 as a trivial example; please mentally substitute with “for example, a bunch of matrix operations to compute a super secret formula result.”

AdmiralAsshat 6y ago

Just in time for the DoJ and the EU to tell them to intentionally cripple it for law enforcement purposes.

r00fus 6y ago

Some of the use cases presented sound like they'd be perfect for DRM.

eternalban 6y ago
Here is a short list of the downsides. I’m sure there is more. Tech is always double edged, it seems. - present false source to claimed binary build of same. - allow for pervasive backdoors in binary blobs that resist scrutiny by security researchers
- csunbird 6y ago
  I don't think that game developers/media companies/etc care about the two things that you have mentioned. All they want is un-crackable DRM.
  - kaszanka 6y ago
    I feel like I'm in way over my head here, but how is it even possible to have mathematically uncrackable DRM? Surely at the end it's going to come down to a comparison instruction (or a few thousand of them), no?
    - avmich 6y ago
      So you want to modify those instructions to crack DRM? Which of them? There is a lot of instructions (say, your few thousand) and even more combinations of instructions, you can't find another combination of instructions which would work.
      - kaszanka 6y ago
        I guess my problem is that I don't see a fundamental difference between this approach and traditional obfuscators/packers/virtualizers/whatever. They can also bloat a simple comparison (for example) into many seemingly useless but interconnected instructions. I just don't understand how it's possible to make a DRM scheme that can't be cracked.

mabbo 6y ago

Nit: Hiding what the neck you're talking about doesn't make for better journalism. If you're going to spend 9 paragraphs talking about the controversy of whether such a thing is possible or not, dedicate at least 1 sentence at the start to explain it. Otherwise it's just confusing because as a reader, I have no idea why I should care or what's even worth caring about here. Recommendation to anyone who hasn't read the article yet: start with the part called "The Crown Jewel".

ksd482 6y ago
Not just Nit, but I think this is a major point. It is my biggest pet peeve and I immediately back off from articles written in such manner. If writers write good introduction paragraph, it gauges my interest and I am more likely to read. Otherwise, I don't read out of spite or protest.
anonunivgrad 6y ago
It’s because journalists have no clue what they’re talking about. This is true for all journalism but you only notice it when it’s about something you’re familiar with.
- bawolff 6y ago
  If you are going to diss the journalist, you should back it up with specific examples.
  - anonunivgrad 6y ago
    I mean journalists in general.
  - adrianmonk 6y ago
    This particular journalist has qualifications that suggest she probably does know what she's talking about. From https://www.quantamagazine.org/authors/erica-klarreich/ https://www.quantamagazine.org/authors/erica-klarreich/: > About the author > Erica Klarreich has been writing about mathematics and science for more than 15 years. She has a doctorate in mathematics from Stony Brook University and is a graduate of the Science Communication Program at the University of California, Santa Cruz.

beatle_sauce 6y ago

Is this basically the learning parity with noise problem, but instead of a fixed size vector, the noisy output is generated in by a PRNG with a pre-determined secret seed? How can this be used for authentication or encryption?

isaacimagine 6y ago

The important point here is that iO, once fully realized, can be used to derive other cryptographic primitives. Fully homomorphic encryption has been doing the rounds for a while now, but it's too slow for practical use - I wonder if this will change that.

some_furry 6y ago

> 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. As someone who works in cryptography, this isn't "The Crown Jewel" of Cryptography. Cryptography to me is about helping queer people live their best life even in countries where they're hated. Cryptography to me is about providing assurance that the software you're running was produced by the people you thought produced it, and that the built binary is reproducible from the source code, which technical people can also inspect to assert the absence of backdoors. Obfuscation and copy-protection are non-goals for me. Fully homomorphic encryption has uses in machine learning and cloud services, but I find them at odds with the goals I care about.

bawolff 6y ago
Arguably aren't those security engineering goals more than cryptography goals?
- some_furry 6y ago
  I'm really not interested in splitting hairs over taxonomy. Real-world cryptography and security engineering intersect a lot.
  - bawolff 6y ago
    i would call both of those the same thing, and neither of them are cryptography.
    - some_furry 6y ago
      Is your argument "real-world cryptography isn't cryptography", or am I misunderstanding? EDIT: I can't reply due to rate-limiting, so here's my reply to your reply below: ----- > My argument is "real world cryptography" is a euphamism for security engineering for people who want to sound more badass. It's not a euphemism. Take a look at the accepted papers at the aptly named Real World Cryptography symposiums: https://rwc.iacr.org/2020/program.html https://rwc.iacr.org/2020/program.html Breaks on OCB2. Lattice attacks on TPMs. MPC research. Privacy-preserving telemetry. I'll accept that you may personally have only seen security engineering work under the guise of "real-world cryptography", but to call it a euphemism is erroneous. ----- > Well if someone wrote an article about the Poincaré conjecture calling it the "crown jewel" of math, and someone else said "actually I consider the primary goal of math to be in helping build low-cost housing and other practical issues," then they're talking about two different things. Both are math, but to say that the Poincaré conjecture isn't important to math because you use math primarily for different things is misleading. All of the proposals for homomorphic encryption I've seen to date (which, for transparency, were mostly in the realm of encrypted databases) don't provide any protection against chosen-ciphertext attacks. If [F]HE isn't IND-CCA2 secure, which is the minimum bar for encryption that should be used outside of academic settings, then calling it the crown jewel only serves to hype up a technology that will fail to protect users.

karmakaze 6y ago

I'm no crypto expert and trying to follow along, but can't make this leap: > But iO is stronger than it sounds. For example, suppose you have a program that carries out some task related to your bank account, but the program contains your unencrypted password, making you vulnerable to anyone who gets hold of the program. Then — as long as there is some program out there that could perform the same task while keeping your password hidden — an indistinguishability obfuscator will be strong enough to successfully mask the password. After all, if it didn’t, then if you put both programs through the obfuscator, you’d be able to tell which obfuscated version came from your original program. Why does existence of another mask the secret? Even if you couldn't distinguish the programs, couldn't you just try both possible secrets?

MauranKilom 6y ago
Suppose there exist two programs that do the same task, with the following properties: - Knowing program A allows an attacker to recover your password. - Program B does not contain any information about your password. Eve knows that these programs exist and that they have these properties. Eve is now given two obfuscated programs O1 and O2. They were produced by applying iO to A and B, but Eve knows neither A, B nor how O1 and O2 map to O(A) and O(B). If it were possible for Eve to somehow obtain your password from, say (without loss of generality), O1 in any way, then Eve could deduce that O1 must be O(A). It could not be O(B) because neither O nor B contain information about your password. Since we assert that indistinguishable obfuscation makes it impossible to draw this kind of conclusion, it must be impossible to obtain your password from O(A) if B exists.
- laszlokorte 6y ago
  I know nothing about the whole topic but could you explain: Why does any of those programs contain the password anyway if it is not needed for achieving the goal? If it is not needed, flow analysis, tree shaking and const evaluation could get rid of it. If it is needed, how would the program not containing it achieve the goal?
  - 6y ago

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 ago
Welcome 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 ago
In 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.

kemonocode 6y ago

@dang, it may be good to de-editorialize the title of this article. Best to simply say that indistinguishability obfuscation has been achieved.

gus_massa 6y ago
He usually prefer the subtitle: A cryptographic master tool called indistinguishability obfuscation has for years seemed too good to be true. Three researchers have figured out that it can work. Reduced to 80 characters it is: 12345678901234567890123456789012345678901234567890123456789012345678901234567890 Three researchers have figured out how indistinguishability obfuscation can work
Ar-Curunir 6y ago
The current title ("iO from Well-Founded Assumptions") is the title of the paper.
- kemonocode 6y ago
  Yeah, that's much better now- definitively wasn't the case when it was submitted though!
  - gus_massa 6y ago
    I remember that the original title was the title of the press article "Computer Scientists Achieve ‘Crown Jewel’ of Cryptography". Sometimes the mods change them.

RcouF1uZ4gsC 6y ago

> Then — as long as there is some program out there that could perform the same task while keeping your password hidden — an indistinguishability obfuscator will be strong enough to successfully mask the password. I wonder if this will be the Achilles heel. If there were a way to perform a task without needing a secret, you would not be using homomorphic encryption. You could just do regular computation since there is no secret. However, if the only way to perform the computation is with the secret, then Indistinguishability Obsfuscation won't help you. To me it seems that iO is useful only for computations that didn't need homomorphic encryption in the first place, because they already had a way to do the computation without the secret.

Ar-Curunir 6y ago
There's been immense applications of iO in crypto already, constructing things we didn't know how to construct from the plain assumptions. This includes primitives which seem, at the first glance, to not have a "secret-less" equivalent.

anonymousisme 6y ago

I can see the malware/ransomware business really wanting this. It would make it impossible to circumvent or decrypt their warez.

bawolff 6y ago
Its already impossible if they implement (plain ole' public key) encryption properly

gumby 6y ago

Doesn't seem like they deal with the 10^6 X slowdowns you encounter with HE. Seems inherent to all the obfuscating computation.

no_identd 6y ago

The IAS about an hour ago uploaded Huijia (Rachel) Lin's talk on this: https://youtu.be/oBhQ58ntjdI https://youtu.be/oBhQ58ntjdI

no_identd 6y ago
Older (2 weeks) video series on this topic: • https://www.youtube.com/watch?v=v2RR_c5hn1E https://www.youtube.com/watch?v=v2RR_c5hn1E • https://www.youtube.com/watch?v=Al7Z53C4OQI https://www.youtube.com/watch?v=Al7Z53C4OQI • https://www.youtube.com/watch?v=8_0Rf0J8p3w https://www.youtube.com/watch?v=8_0Rf0J8p3w