UCLA computer grad constructs “crown jewel of cryptography” • Hacker News Board

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

#141

Post by DannyBee » Fri, May 26, 2023, 6:10 PM UTC

pelorat wrote: post #132

DannyBee wrote: post #97

Earlier quoted context omitted.

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…

> You can't tell A is a bubble sort at all, and you can't tell B is a selection sort at all. That doesn't make any sense. You can trace them while they execute, then compare and analyze the two traces? By definition obfuscation is always reversible or the software wouldn't even work any more. You can make it infeasible (timewise) to figure it out, but it's still possible, even if it takes infinite time.

I'd suggest reading the paper - which covers this ;)

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

#142

Post by codethief » Fri, May 26, 2023, 6:37 PM UTC

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…

> 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.

I don't understand. Shouldn't a different secret key yield a different function / circuit?

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

#143

Post by DannyBee » Fri, May 26, 2023, 8:42 PM UTC

codethief wrote: post #142

DannyBee wrote: post #102

Earlier quoted context omitted.

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…

> 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. I don't understand. Shouldn't a different secret key yield a different function / circuit?

You can actually do it both ways - where the ciphertext is an obfuscated program, and where keys a programs and ciphertexts are short.

https://eprint.iacr.org/2013/454.pdf and friends have a direct description of the latter and references to the former.

This is just one mechanism.

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

#144

Post by DannyBee » Fri, May 26, 2023, 8:46 PM UTC

dataflow wrote: post #130

DannyBee wrote: post #97

Earlier quoted context omitted.

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…

I'm kind of confused. I'm guessing this is a dumb question, but I'm obviously missing something. If a program is running bubble sort, and another is running selection sort... can't you just run them instruction-by-instruction to see which elements they swap? And deduce what they were based on that? Like if you have [4, 3, 2, 1], and the first swap the program does results in [1, 3, 2, 4], then it clearly wasn't bubbl…

Boolean circuits themselves do not have memory. (though you can create memory within them).

See the formal model here: https://en.wikipedia.org/wiki/Circuit_(computer_science)

There are extensions of iO to RAM programs, but this is not it.

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

#145

Post by sacnoradhq » Sat, May 27, 2023, 2:23 AM UTC

Animats wrote: post #2

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…

Autonomous, polymorphic malware utilizing secure computation to perform operations that aren't revealed to systems they infect.

Seems like there is an opportunity for bot nets to perform computations, say BTC mining, in a completely sealed and zero-knowledge environment, which now may not even need a backdoor or are able to hide it perfectly.