5 ms·

Is it just an existence proof or is it actually constructive? (I haven't read the dissertation.)

vlovich123 3y ago
Looks like constructive but my math knowledge is probably equivalent to a freshman’s at best.
matthewdgreen 3y ago
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.
Animats 3y ago
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.
- scarmig 3y ago
  Can't finite iteration and recursion just be unrolled? And storage just considered another part of the input?
  - grayhatter 3y ago
    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.
    - User23 3y ago
      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.
  - jahewson 3y ago
    This is how SMT solvers deal with bounded quantifiers.
- dmix 3y ago
  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
  - whatshisface 3y ago
    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...
    - whitemary 3y ago
      > people already cannot tell whether code has backdoors I was feeling crazy after reading that.
  - tivert 3y ago
    > 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#Classified_discovery https://en.wikipedia.org/wiki/Public-key_cryptography#Classi..., differential cryptanalysis: https://en.wikipedia.org/wiki/Differential_cryptanalysis#History https://en.wikipedia.org/wiki/Differential_cryptanalysis#His...).
    - withinboredom 3y ago
      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.
  - KMag 3y ago
    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.
- x-complexity 3y ago
  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.
  - anonymousDan 3y ago
    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)?
- jhanschoo 3y ago
  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 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 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.
- ihm 3y ago
  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.
deleted 3y ago
[deleted]

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

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.

Animats 3y ago

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.

scarmig 3y ago
Can't finite iteration and recursion just be unrolled? And storage just considered another part of the input?
- grayhatter 3y ago
  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.
  - User23 3y ago
    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.
- jahewson 3y ago
  This is how SMT solvers deal with bounded quantifiers.
dmix 3y ago
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
- whatshisface 3y ago
  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...
  - whitemary 3y ago
    > people already cannot tell whether code has backdoors I was feeling crazy after reading that.
- tivert 3y ago
  > 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#Classified_discovery https://en.wikipedia.org/wiki/Public-key_cryptography#Classi..., differential cryptanalysis: https://en.wikipedia.org/wiki/Differential_cryptanalysis#History https://en.wikipedia.org/wiki/Differential_cryptanalysis#His...).
  - withinboredom 3y ago
    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.
- KMag 3y ago
  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.
x-complexity 3y ago
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.
- anonymousDan 3y ago
  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)?
jhanschoo 3y ago
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 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 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.
ihm 3y ago
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.

deleted 3y ago

[deleted]