3 ms·
Is there a conjecture that says for a field with given a degree of complexity, a given string or function of a can be encoded equivalently in a number of differ
by motohagiography 5y ago
Is there a conjecture that says for a field with given a degree of complexity, a given string or function of a can be encoded equivalently in a number of different ways that is proportional to its size and maybe complexity class?
Between this and project zero's analysis (https://news.ycombinator.com/item?id=29568625 https://news.ycombinator.com/item?id=29568625) of NSO using compression encoding to create a virtual machine for calculating exploit offsets, while unrelated except at a very high level of abstraction, it reminds me conceptually of cryptographic hash collisions, where over a large enough search space or field / domain of complexity there are many equivalent encodings or homonyms/isomorphisms.
The issue with the NSO exploit was they found that the compression encoding for a font was Turing complete, and then wrote a virtual architecture in it, and then ran programs on it that did the calculations necessary for their exploit.
This png encoding issue is different, but if you abstract it upwards to find a general principle it may be the effect of, it's like there is fast rule where if if you know the size or definition of the field of possibilities, and then have a definition of a given string in it, the function that describes or defines that string will also yield all strings whose evaluation is the same. It's like Kolmolgorov complexity, but where instead of finding the smallest progam to compute something, it's: given the number of instructions to define programs over a field of inputs of a given size, there are N programs beneath length L that are equivalent.
Sort of a showerthought, but it's interesting to think that our ideas of encodings and general isomorphisms may be instances of the same concept linked by a sort of "imaginary" function.
- Jerrrry 5y agohttps://en.wikipedia.org/wiki/Verifiable_computing https://en.wikipedia.org/wiki/Verifiable_computing
- motohagiography 5y agoWow, thank you. Totally forgot about FHE, this is the underlying principle of why FHE must work theoretically.