4 ms·

Making an invertible function out of non-invertible parts

71 points by chmaynard 7y ago

fyp 7y ago
An unexpected application of feistel network is for creating neural networks that are invertible! https://arxiv.org/abs/1802.07088 https://arxiv.org/abs/1802.07088
- fvncc 7y ago
  Another example is RealNVP, which has the same structure to enable inversion (partition, process half, then use the result to mutate the other half in an invertible way). Sadly, I gather the computational performance Is pretty bad .. https://arxiv.org/abs/1605.08803 https://arxiv.org/abs/1605.08803
- visarga 7y ago
  Interesting, I was aware of this technique in deep learning but didn't know its origin!
thaumasiotes 7y ago
This is a weird headline. It amounts to the claim that f(x) = x + 3 is made from non-invertible parts because its "subcomponent" g(x) = 3 is non-invertible. But who cares? Our f(x) is as conceptually simple as an invertible function can be. If we're going to consider it to have been assembled from non-invertible parts, then what's interesting about the fact that an invertible function can be assembled from non-invertible parts? It's impossible to define any function, invertible or not, without using non-invertible parts -- by this definition.
- joppy 7y ago
  I think this is pretty dismissive of what the author is trying to explain: the round functions for ciphers are non-invertible, and there is a construction which strings them together such that the whole thing is invertible. That’s pretty interesting! Your example is also poorly chosen. f(x) = x + 3 is invertible because it is the composition of two invertible functions, the identity (x => x) and the add-three function (x => x + 3). If we took your f(x) = x + g(x) example, it would be non-invertible for many g, for example when g(x) = -x. So I think there really is something to be said for “assembling an invertible function out of non-invertible parts”.
  - thaumasiotes 7y ago
    > what the author is trying to explain: the round functions for ciphers are non-invertible, and there is a construction which strings them together such that the whole thing is invertible. That’s pretty interesting! But this is just incorrect as a description of the article. The round functions for ciphers are not non-invertible. They're invertible individually, and that's why the overall cipher, which consists of chaining them together, is also invertible. In order to invert a single round cipher, you need to know f(R_{n-1}, K_n). R_{n-1} is given, and by hypothesis you possess the key K_n, so you do know this value. f(R_{n-1}, K_n) is the function identified as non-invertible, not the round cipher. It doesn't matter at all whether it's non-invertible, because you don't run it backward. You run it forward. In your example, if we have f(x) = x + g(x), and we analogously have knowledge of the input to g, it still doesn't matter whether, in the absence of that knowledge, f(x) is invertible or not. Since we know the value of g(x), we can invert f(x), because f(x) is a single application of a trivially invertible function. (f(x) = x + g(x), where g(x) is constant.) Using your example, when f(x) = x + g(x), g(x) = -x, and I know that f(x) = 0 and g(x) is 5, I can easily invert f(x): x is -5. My example was specifically suggested by the article: > Here ⊕ is bitwise XOR (exclusive or) and f(R_{n-1}, K_n) is any function of the previous right sub-block and the key for the nth round. The function f need not be invertible. It could be a hash function. It could even be a constant, crushing all input down to a single value. It is one of the non-invertible parts that the system is made of. (My emphasis.) In fact, it is the only non-invertible part in the system as described. If we keep the example of f(x) = x + 3, what you're saying above is that this function cannot be inverted by someone who knows that f(x) takes the form f(x) = x + g(x), but doesn't know that g(x) = 3. That's true, but -- once again -- I don't see how it means that f(x) is "made from non-invertible parts" in any way that every other function doesn't also satisfy. > f(x) = x + 3 is invertible because it is the composition of two invertible functions, the identity (x => x) and the add-three function (x => x + 3) This is begging the question. You just said that f is invertible because (1) it is the composition of f with the identity function [true - that is the definition of the identity function]; (2) the identity function is invertible [true again!]; (3) f is invertible [oops]. We can boil that down to "f is invertible because it is". In fact, f is invertible because it is one-to-one -- f(a) = f(b) if and only if a = b.
- jsinai 7y ago
  Actually g(x) = 3 is multiplicatively and additively invertible.
  - wizzwizz4 7y ago
    g(x) = 3, alone, is not. I give you 3, and there's no possible way you're telling me what the original x value was. f(x) = x ⋄ g(x) is (for ⋄ in {+, ×}), but that's a different matter entirely.
  - Spivak 7y ago
    If I pick an x and tell you that g(x) = 3 can you tell me what x is?
- deleted 7y ago
  [deleted]
nayuki 7y ago
The article talks about Feistel networks and the most famous Feistel cipher, DES. I wrote a spreadsheet where you can examine every bit of the computation of DES encryption: https://www.nayuki.io/page/des-cipher-internals-in-excel https://www.nayuki.io/page/des-cipher-internals-in-excel

71 points by chmaynard 7y ago

fyp 7y ago

An unexpected application of feistel network is for creating neural networks that are invertible! https://arxiv.org/abs/1802.07088 https://arxiv.org/abs/1802.07088

fvncc 7y ago
Another example is RealNVP, which has the same structure to enable inversion (partition, process half, then use the result to mutate the other half in an invertible way). Sadly, I gather the computational performance Is pretty bad .. https://arxiv.org/abs/1605.08803 https://arxiv.org/abs/1605.08803
visarga 7y ago
Interesting, I was aware of this technique in deep learning but didn't know its origin!

thaumasiotes 7y ago

This is a weird headline. It amounts to the claim that f(x) = x + 3 is made from non-invertible parts because its "subcomponent" g(x) = 3 is non-invertible. But who cares? Our f(x) is as conceptually simple as an invertible function can be. If we're going to consider it to have been assembled from non-invertible parts, then what's interesting about the fact that an invertible function can be assembled from non-invertible parts? It's impossible to define any function, invertible or not, without using non-invertible parts -- by this definition.

joppy 7y ago
I think this is pretty dismissive of what the author is trying to explain: the round functions for ciphers are non-invertible, and there is a construction which strings them together such that the whole thing is invertible. That’s pretty interesting! Your example is also poorly chosen. f(x) = x + 3 is invertible because it is the composition of two invertible functions, the identity (x => x) and the add-three function (x => x + 3). If we took your f(x) = x + g(x) example, it would be non-invertible for many g, for example when g(x) = -x. So I think there really is something to be said for “assembling an invertible function out of non-invertible parts”.
- thaumasiotes 7y ago
  > what the author is trying to explain: the round functions for ciphers are non-invertible, and there is a construction which strings them together such that the whole thing is invertible. That’s pretty interesting! But this is just incorrect as a description of the article. The round functions for ciphers are not non-invertible. They're invertible individually, and that's why the overall cipher, which consists of chaining them together, is also invertible. In order to invert a single round cipher, you need to know f(R_{n-1}, K_n). R_{n-1} is given, and by hypothesis you possess the key K_n, so you do know this value. f(R_{n-1}, K_n) is the function identified as non-invertible, not the round cipher. It doesn't matter at all whether it's non-invertible, because you don't run it backward. You run it forward. In your example, if we have f(x) = x + g(x), and we analogously have knowledge of the input to g, it still doesn't matter whether, in the absence of that knowledge, f(x) is invertible or not. Since we know the value of g(x), we can invert f(x), because f(x) is a single application of a trivially invertible function. (f(x) = x + g(x), where g(x) is constant.) Using your example, when f(x) = x + g(x), g(x) = -x, and I know that f(x) = 0 and g(x) is 5, I can easily invert f(x): x is -5. My example was specifically suggested by the article: > Here ⊕ is bitwise XOR (exclusive or) and f(R_{n-1}, K_n) is any function of the previous right sub-block and the key for the nth round. The function f need not be invertible. It could be a hash function. It could even be a constant, crushing all input down to a single value. It is one of the non-invertible parts that the system is made of. (My emphasis.) In fact, it is the only non-invertible part in the system as described. If we keep the example of f(x) = x + 3, what you're saying above is that this function cannot be inverted by someone who knows that f(x) takes the form f(x) = x + g(x), but doesn't know that g(x) = 3. That's true, but -- once again -- I don't see how it means that f(x) is "made from non-invertible parts" in any way that every other function doesn't also satisfy. > f(x) = x + 3 is invertible because it is the composition of two invertible functions, the identity (x => x) and the add-three function (x => x + 3) This is begging the question. You just said that f is invertible because (1) it is the composition of f with the identity function [true - that is the definition of the identity function]; (2) the identity function is invertible [true again!]; (3) f is invertible [oops]. We can boil that down to "f is invertible because it is". In fact, f is invertible because it is one-to-one -- f(a) = f(b) if and only if a = b.
jsinai 7y ago
Actually g(x) = 3 is multiplicatively and additively invertible.
- wizzwizz4 7y ago
  g(x) = 3, alone, is not. I give you 3, and there's no possible way you're telling me what the original x value was. f(x) = x ⋄ g(x) is (for ⋄ in {+, ×}), but that's a different matter entirely.
- Spivak 7y ago
  If I pick an x and tell you that g(x) = 3 can you tell me what x is?
deleted 7y ago
[deleted]

nayuki 7y ago

The article talks about Feistel networks and the most famous Feistel cipher, DES. I wrote a spreadsheet where you can examine every bit of the computation of DES encryption: https://www.nayuki.io/page/des-cipher-internals-in-excel https://www.nayuki.io/page/des-cipher-internals-in-excel