4 ms·
AD reminds me of another idea: in cryptography, you can determine eg. how bit dependencies propagate through a state vector by running the regular code for your
by edflsafoiewq 8y ago
AD reminds me of another idea: in cryptography, you can determine eg. how bit dependencies propagate through a state vector by running the regular code for your compression function or whatever, but on "numbers" that actually track the dependencies of bits. Details vary, but a simple idea is to use as a "number" a vector of symbolic equations for each bit in the number in terms of symbolic variables for input bits to the function. You can then easily calculate items of interest eg. at this many rounds, has every input bits affected every output bit?
So, jets instead of numbers for differentiation, systems of boolean equations instead of numbers for answering some crypto questions... anyone know of other tricks in this vein?
- CardenB 8y agoThere’s definitely some work of tracking activations in a network for a given set of inputs. It’s a good black-box way to prune your network for lighter weight models.
- xKingfisher 8y agoThe KLEE project[1] does something similar for general code, with symbolic variables. [1] http://klee.github.io http://klee.github.io
- tnecniv 8y agoDo you have a reference for the crypto trick you described?
- aaaaaaaaaab 8y agoTaint checking: https://en.m.wikipedia.org/wiki/Taint_checking https://en.m.wikipedia.org/wiki/Taint_checking Every external input to a program is assumed “tainted”. There are certain operations that make them “safe” (e.g. escaping a string makes it safe against SQL injection, etc.). You simply attach this “tainted/safe” bit of information to each piece of data and flow it through your program. There is a simple calculus for combining these tainted/safe values, i.e. appending a tainted string to a safe string produces a tainted string, etc. The goal is to prove that tainted values can’t make it to the business logic, so that your program is safe against certain kinds of malicious input.
- goldenkey 8y agoWould you mind providing a reference to this technique? I recently got into theoretical cryptography and am quite interested in any analytical tools.
- YorkshireSeason 8y agoI would be surprised if there was any crypto where not any output bit depended on any input bit (of course it depends on what precisely one means by "depends upon"). Otherwise, couldn't the search-space be partitioned? See also: Shannon's confusion and diffusion principle [1], as well as the avalanche effect [2]. [1] https://en.wikipedia.org/wiki/Confusion_and_diffusion https://en.wikipedia.org/wiki/Confusion_and_diffusion [2] https://en.wikipedia.org/wiki/Avalanche_effect https://en.wikipedia.org/wiki/Avalanche_effect
- profquail 8y agoWhat you’re describing sounds like Abstract Interpretation[1], a technique used in static analyzers and compilers (e.g. for bounds-check elimination). You can pick any abstract domain you want, but the more complex the domain — i.e., the more complex/precise your tracking of the possible values associated with each variable — the longer it takes for the analysis to run. [1]: https://en.m.wikipedia.org/wiki/Abstract_interpretation https://en.m.wikipedia.org/wiki/Abstract_interpretation
- edflsafoiewq 8y agoAbstract interpretation would be the equivalent of symbolic differentiation in this analogy.
- antidesitter 8y agoSounds like higher-order differential cryptanalysis: https://en.wikipedia.org/wiki/Higher-order_differential_cryptanalysis https://en.wikipedia.org/wiki/Higher-order_differential_cryp...