Hacker News Reader

Comment by dataflow | Hacker News Reader

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, compute an input which yields them) by trying all the input patterns.. There's no undecidability and no halting problem. There's just difficulty. "Difficult" here means there's no way easier than trying all the patterns. This is the same property sound cryptosystems are supposed to have - there's no easier way than trying all the keys.

Whether this result can be extended to programs with iteration I'm not sure. The paper doesn't seem to mention iteration or storage.

A (polynomial-sized) circuit in this context is a sequence of DAGs whose nodes are binary logic gates where the nth DAG infers 1 output bit from n input bits, such that some polynomial bounds the size of the graphs of the sequence. See https://en.wikipedia.org/wiki/Circuit_complexity

The class of circuits in question is P/poly which includes BPP (which includes P, the class of polynomial-time programs). So the result is quite general, since most practical programs are in P.

For an introduction to complexity theory, see Arora, Barak (2009) (Draft available here https://theory.cs.princeton.edu/complexity/book.pdf ); same Barak that did the presentation "On the (Im)Possibility of Obfuscating Programs" (2001) mentioned in the abstract.

IMO: Paranoid about the implications, slightly less worried about it applying in practice.

As shown by the DRM schemes used in modern games, this type of obfuscation comes at the cost of performance: Unless you want to compute a sensitive function at the user's end in an obfuscated manner, it'd be much simpler to just run that function on your end and optimize it in terms of running costs & performance.

Such a design would also runs counter to the everything-as-a-service model that companies are trending towards, as it places more power back at the user's end, even if the user can't decipher the obfuscated function's inner mechanisms. Such a design would reduce the need to phone home, and thus the need for EaaS.

Would it be possible to use this to obfuscate other cryptographic primitives (e.g. a hash function or a simple program that checks whether the hash of some input equals a hardcoded value)?

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

Because figuring out what a worm does doesn't help if it has already done it, and for that matter they're supposed to remain undetected. Furthermore people already cannot tell whether code has backdoors, or what ML classifiers do for that matter.

Unfortunately, the biggest industrial use case is making wi-fi routers that are absolutely impossible to install OpenWRT on, etc...

> people already cannot tell whether code has backdoors

I was feeling crazy after reading that.

> 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 cryptanalysis: https://en.wikipedia.org/wiki/Differential_cryptanalysis#His...).

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.

There are more efficient ways to hide malware from current scanners, and on the flip-side, the scanners that use heuristics/ML to classify the sequence of system calls made by the binary wouldn't be affected by this sort of obfuscation.

As mentioned on page 9 of the thesis, IO as constructed in the thesis implies IO for RAM machines, so yes you can do programs with iteration.

Can't finite iteration and recursion just be unrolled? And storage just considered another part of the input?

This is how SMT solvers deal with bounded quantifiers.

In theory? Absolutely; unrolling a loop is exactly what it sounds like. Recursion is just a fancy loop. But there's a reason no one does that, and why no compilers emit that as code.

Fancy in the sense of being a loop with an implicit stack. Or maybe just some registers if TCO.

And yet the machines we can actually build are far closer to LBAs than TMs.

It is not efficient enough that you need to worry about exciting developments using this scheme. But it’s a step towards more reasonable mathematical assumptions than previous constructions, assumptions that may actually be true. Give it a few more years and we might be able to use this stuff.

Looks like constructive but my math knowledge is probably equivalent to a freshman’s at best.

Reply on news.ycombinator.com