i was just thinking about this in the shower and came up with this handwaving justification: if you have two random values, using AND biases the number of set

i was just thinking about this in the shower and came up with this handwaving justification: if you have two random values, using AND biases the number of set bits on average (you get 3/4 zeroes in the output). in other words, it lowers the (shannon) entropy in the circuit, on average, while an invertible function preserves entropy (it has to, right?). entropy sounds like a smart thing to preserve in a PRF so this would seem like an argument for invertibility. BUT it's only preserving entropy on average, and what you really care about is the entropy in the difference between input and ouptut in any single round. which is not the same thing at all (identity function is great for the former, not so good for the latter). so you could imagine there's some trade-off... forgive me if this makes no sense. it just seemed interesting when i thought of it :o)