[Cryptography] Simple non-invertible function?

[John Denker]

There are at least four different concepts on the table.
 a) Non-invertible function.
 b) One-way function.
 c) One-way permutation.
 d) Backtrack resistance.
 *) various less-relevant possibilities

In cryptography, there is a rather detailed technical
definition of "one-way function" ... and the details
are important.

One-way /permutations/ are of particular importance,
because they preserve entropy.

I'll let Sandy speak for himself, but given the context
I suspect that the application calls for a backtrack
resistant one-way permutation ... not just any old
non-invertible function.

As others have pointed out, multiplication by zero is
a simple (!) non-invertible function according to the 
usual definition, but not very useful in the context 
of RNGs or crypto in general.

On 09/15/2014 10:12 AM, Sandy Harris wrote:

> 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?

---> What is the intended application?

On 09/19/2014 08:15 PM, John Gilmore wrote:

>> OK, so make a secure block cipher with a 16-bit block.  Do 
>> "encrypt(x, key) xor x".  Sandy says that this is somehow magically
>> non-invertible, but if I just run it for every value of X (all
>> 65536 of them), I can build a table that DOES let me invert it.

As Henny Youngman would say:  So don't do it that way.
Choose a bigger blocksize, so that brute-force lookup 
tables are infeasible.  Ditto for rainbow tables.