Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

UCLA computer grad constructs “crown jewel of cryptography”

acm.org

Post reply on HN
Print view View original

101–110 of 145 posts

Re: UCLA computer grad constructs “crown jewel of cryptography”

#101

Post by gnull »

hkopp wrote: post #69

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…

The latter is useful to hide who wrote the program? Like some features of code that might reveal your personal patterns?

Or what is it for?

And how does it deal with timing? İf two programs I gave it have different complexity, would it pad the running time to some fixed value? İf so, how is that value chosen?

Re: UCLA computer grad constructs “crown jewel of cryptography”

#102

Post by DannyBee »

Waterluvian wrote: post #100
DannyBee wrote: post #98

Earlier quoted context omitted.

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.

And that involves preventing the leakage of any data? Such as the time each take?

The original goal was to be able to make public key systems out of secret key systems, so hiding existing running time is not part of the definition of indistinguishable.

It is about what information you can glean about either of the originals. Formally (from the paper):

Indistinguishability: For every two ensembles {C0,λ} and {C1,λ} of polynomial-sized circuits that have the same size, input length, and output length, and are functionally equivalent, that is, ∀λ, C0,λ(x) = C1,λ(x) for every input x, the following distributions are computationally indistinguishable:

  {iO(1λ, C0,λ)} {iO(1λ, C1,λ)}
IE you can take a secret key system, hardwire the key into the program, and turn it into a public key system without fear that the secret key will be recovered - instead, it will not be distinguishable from other programs with different hardwired keys.

Re: UCLA computer grad constructs “crown jewel of cryptography”

#103

Post by Waterluvian »

DannyBee wrote: post #102
Waterluvian wrote: post #100

Earlier quoted context omitted.

And that involves preventing the leakage of any data? Such as the time each take?

The original goal was to be able to make public key systems out of secret key systems, so hiding existing running time is not part of the definition of indistinguishable. It is about what information you can glean about either of the originals. Formally (from the paper): Indistinguishability: For every two ensembles {C0,λ} and {C1,λ} of polynomial-sized circuits that have the same size, input length, and output lengt…

Ah I think I understand better. Thanks!

Re: UCLA computer grad constructs “crown jewel of cryptography”

#104

Post by liminvorous »

Xelynega wrote: post #81
Brotkrumen wrote: post #64

Earlier quoted context omitted.

"This is a trade secret. We have not patented it, because it's so clever and valuable that it needs to be protected longer than a patent lasts"

Except we know(and have example from cryptocurrency) that the problems with ownership in real life have little to do with cryptography. The reason coca cola doesn't use Pepsi's recipe isnt because mixing the ingredients under heat creates an irreversible mixture that you can seperate to find the recipe. They don't use pepsis recipe because its illegal.

You can't copyright a recipe, the thing reason it doesn't make sense for Pepsi to make an exact duplicate of coke is that Coke is better at selling Coke that Pepsi is, and it's better for them to be a niche alternative some people prefer than to be an undifferentiated competititor. Reverse engineering trade secrets is perfectly legal if you haven't agreed otherwise.

Re: UCLA computer grad constructs “crown jewel of cryptography”

#105

Post by junon »

DannyBee wrote: post #97
hkopp wrote: post #69

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…

To try to make this concrete, if you have a program A that does bubble sort, and a program B that does selection sort: 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 cas…

Thanks, this is a great explanation.

Re: UCLA computer grad constructs “crown jewel of cryptography”

#106

Post by withinboredom »

tivert wrote: post #57
dmix wrote: post #31

Earlier quoted context omitted.

The next question is why didn’t the high end shops spending a ton of money and recruiting effort on crypto and state malware like NSA .. or Russia(?) figure this out already or did they

> The next question is why didn’t the high end shops spending a ton of money and recruiting effort on crypto and state malware like NSA .. or Russia(?) figure this out already or did they There's no way to know. But the NSA (at least) has a documented history of making crypto breakthroughs and keeping them secret (e.g. public key crypto: https://en.wikipedia.org/wiki/Public-key_cryptography#Classi... , differential c…

The fun open secret about working as a researcher for the NSA is that even after you leave the NSA, any and all research must be approved by them before publishing.

Re: UCLA computer grad constructs “crown jewel of cryptography”

#107

Post by dilippkumar »

DannyBee wrote: post #98
codethief wrote: post #87

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.

How far does this analogy go?

For example, if I plot how long both programs take at various scales, at some point I should be able to determine which one is O(n log(n)) right?

Re: UCLA computer grad constructs “crown jewel of cryptography”

#108

Post by ronsor »

Sophistifunk wrote: post #29

If mankind can't stomach 10% overhead to check array bounds and collect unused memory, what makes anybody think they can sell 1,000,000% overhead to make your DRM driver (and viruses) harder to reverse?

Denuvo would like a word with you.

Re: UCLA computer grad constructs “crown jewel of cryptography”

#109

Post by DannyBee »

dilippkumar wrote: post #107
DannyBee wrote: post #98

Earlier quoted context omitted.

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.

How far does this analogy go? For example, if I plot how long both programs take at various scales, at some point I should be able to determine which one is O(n log(n)) right?

I gave the formal definition of distinguishability in the other comment, but it does not include running time.

Re: UCLA computer grad constructs “crown jewel of cryptography”

#110

Post by andrewflnr »

liminvorous wrote: post #104
Xelynega wrote: post #81

Earlier quoted context omitted.

Except we know(and have example from cryptocurrency) that the problems with ownership in real life have little to do with cryptography. The reason coca cola doesn't use Pepsi's recipe isnt because mixing the ingredients under heat creates an irreversible mixture that you can seperate to find the recipe. They don't use pepsis recipe because its illegal.

You can't copyright a recipe, the thing reason it doesn't make sense for Pepsi to make an exact duplicate of coke is that Coke is better at selling Coke that Pepsi is, and it's better for them to be a niche alternative some people prefer than to be an undifferentiated competititor. Reverse engineering trade secrets is perfectly legal if you haven't agreed otherwise.

Since when is coca cola niche?
Post reply on HN