Unkeyed, fast, one-way PRP Are there any fast, secure, one-way, unkeyed almost-pseudorandom permutations? I am looking for something that can hide a MAC, without requiring a secret key and while being much faster than public key crypto.  It is important that it is a almost-PRP, not a PRF.

By "almost-PRP", I mean "a one-to-one function that is also preimage resistant"
There is a misconception here regarding the security of MACs. It is certainly not true that MACs give away the secret key if it is known and the key reused. You are thinking about information-theoretic MACs (or possibly GHASH). However, a secure MAC does not have any problem at all. You can use HMAC or CMAC or even GMAC, and these are secure for many MACs even if the adversary sees many pairs of message/tag (and even if the adversary can choose what messages to get MACed). So, in answer to your question:


It is impossible to have an (almost) pseudorandom permutation without a secret key. You can heuristically use a hash function as a random oracle, but this opens up another big discussion
You do not need such an object for what you want. Just use a normal secure MAC and it is safe.