[Cryptography] Simple non-invertible function?

[Christian Huitema]

>> Preneel et al., in a paper on block-cipher-based hashes, prove that
>> encrypt(X,key) XOR X and various related structures are
>> non-invertible.
>
> Yes, but is it backtrack resistant?  Is it a permutation?
> Does it preserve entropy?

For the general case, you would have to demonstrate that for a given Encrypt
function there is no tuple (X, Y, key) such that encrypt(X,key) XOR X =
encrypt(Y,key) XOR Y.

Let's do a simple example. Assume encrypt(X,key) = X^key, i.e. a very simple
"encryption" function. Then encrypt(X,key) XOR X = key = encrypt(Y,key) XOR
Y for all (X, Y, key). So we have at least one example where the construct
does not provide a permutation.

Even for less trivial encryption functions, it would take some time to
demonstrate the absence of collisions.

-- Christian Huitema