91–100 of 145 posts
That is a fascinating result. A remarkable mathematical achievement. And a nightmare. This thesis says that it's possible to obfuscate code in such a way that there is a lower bound on the level of effort needed to de-obfuscate it. That lower bound can apparently be comparable to the level of effort required to break a cryptosystem. So, coming soon, viruses and worms nobody can figure out. Code where no one can tell…
That is a fascinating result. A remarkable mathematical achievement. And a nightmare. This thesis says that it's possible to obfuscate code in such a way that there is a lower bound on the level of effort needed to de-obfuscate it. That lower bound can apparently be comparable to the level of effort required to break a cryptosystem. So, coming soon, viruses and worms nobody can figure out. Code where no one can tell…
Earlier quoted context omitted.
Is it just an existence proof or is it actually constructive? (I haven't read the dissertation.)
I'm not sure. It seems to be applied to "circuits", which in this context seems to mean a one-way set of logic gates (such as AND, OR, NOT, NAND) which map a set of boolean inputs to a set of boolean outputs. In theory you can construct any finite digital function that way. It's a useful abstraction, like a Turing machine. Unlike a Turing machine, a circuit is finite. All circuits are "solveable" (given a outputs, co…
Earlier quoted context omitted.
> while obfuscation is used to hide something from the intended recipient. No. Most obfuscation is done to increase the time needed to reverse the source of publicly available programs. Not the user (99% of the recipients) but the adversary is the intended target. The users are just cought in the crossfire. Unless you consider every user of apps as someone who has both the skill and the need to reverse engineer your…
> No. Most obfuscation is done to increase the time needed to reverse the source of publicly available programs. So to stop the intended recipient from deciphering the program. "Adversaries" are the strawman used to hurt legitimate customers who are left with black boxes for device drivers and no functioning hardware since the manufacturers make it impossible to open source firmware updates.
I share the sentiment that in most cases it just serves DRM vendors and is disservice to users but that's not all the cases.
That is a fascinating result. A remarkable mathematical achievement. And a nightmare. This thesis says that it's possible to obfuscate code in such a way that there is a lower bound on the level of effort needed to de-obfuscate it. That lower bound can apparently be comparable to the level of effort required to break a cryptosystem. So, coming soon, viruses and worms nobody can figure out. Code where no one can tell…
What you are worried about is VBB (roughly can i take a program a and obfuscate it in a way that you get no information about the original from the obfuscated version), which has been proven impossible.
This is about indistinguishability, which is a form of obfuscation, but not the kind you are thinking about.
This is really something like "If you have two programs a and b that compute the same function, it's possible to obfuscate them in a way that the resulting programs are indistinguishable from each other"
So if program a is "bubble sort" and program b is "selection sort" (function here is the mathematical sense, so these compute the same function), obfuscation can make it so you can't tell them from each other, and you can't tell if the original program of what you are holding was bubble or selection .
Roughly: VBB is the ability to take any program and make it indistinguishable from random.
IO is the ability to take two programs that compute the same function and make them indistinguishable from each other.
"compute the same function" is actually what makes it feasible :)
The original use case was really trying to turn secret key systems into public key systems by hardwiring the secret key into the program and then obfuscating it.
So an example use case today would be "every DVD decoding program has a different key but computes the same function, can you make them all indinguishtable and thus hide the key" or something like that.
That is a fascinating result. A remarkable mathematical achievement. And a nightmare. This thesis says that it's possible to obfuscate code in such a way that there is a lower bound on the level of effort needed to de-obfuscate it. That lower bound can apparently be comparable to the level of effort required to break a cryptosystem. So, coming soon, viruses and worms nobody can figure out. Code where no one can tell…
Just don't trust that code, and don't run it? You should require positive proof that code does what you want. Similar to how eg Haskell's type systems doesn't have to solve the halting problem [0]: it just rejects some programs that would be ok, but don't conform to the type system. See also proof-carrying code. https://en.wikipedia.org/wiki/Proof-carrying_code [0] Ok, unless you use undecidable instances or somethin…
The precise mathematical definition of obfuscation and what is considered obfuscation for an average software engineer are two very different things. In fact, the article is only about indistinguishability obfuscation. What is mostly discussed in this thread is the notion of virtual black box obfuscation (VBB). VBB has been proven to be impossible in the general case (see https://www.wisdom.weizmann.ac.il/~oded/PS/ob…
1. VBB would be making it so you can't glean information about A or B by running VBB(A) or VBB(B) or examining them, for various definitions of "information".
You can't tell A is a bubble sort at all, and you can't tell B is a selection sort at all.
VBB is, as mentioned, impossible in the general case.
2. IO would be making it so if you are holding IO(A) and IO(B), you can't tell them apart, and can't tell if the original was A or B.
So you can have functionally identical programs, and when you run them through IO, you can't tell whether the original was A or B.
The precise mathematical definition of obfuscation and what is considered obfuscation for an average software engineer are two very different things. In fact, the article is only about indistinguishability obfuscation. What is mostly discussed in this thread is the notion of virtual black box obfuscation (VBB). VBB has been proven to be impossible in the general case (see https://www.wisdom.weizmann.ac.il/~oded/PS/ob…
Thanks, I had no idea what to make of the OP, so your comment is very valuable! > Or put in different words, I don't see how the second phrasing follows from the first one. In fact, I don't understand what the second statement is supposed to mean to begin with. Could you elaborate?
Roughly: VBB is the ability to take any program and make it indistinguishable from random.
IO is the ability to take two programs that compute the same function and make them indistinguishable from each other.
Weird how having research of this quality only lands you assistant professorship. The competition in academia is insane
It's not weird, it's how academia works, it's not even about competition, it's about putting in the work in a sustained manner. It's about proving if you can get funding (who do you know, how often do you publish, what type of publishing do you do), how long have you been teaching for, etc etc. In addition to experience, most institutions have specific criteria and expectations for promotion to full professorship...…
Earlier quoted context omitted.
Thanks, I had no idea what to make of the OP, so your comment is very valuable! > Or put in different words, I don't see how the second phrasing follows from the first one. In fact, I don't understand what the second statement is supposed to mean to begin with. Could you elaborate?
If you have a bubble sort and selection sort, and run them through IO, for either result, you can't tell if the original was bubble sort or selection sort. Roughly: VBB is the ability to take any program and make it indistinguishable from random. IO is the ability to take two programs that compute the same function and make them indistinguishable from each other.