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"

  • $\begingroup$ What exactly do you mean with "hide a MAC"? A MAC is normally indistinguishable from random if the key is secret. If you want to make the same input generate a different MAC then you need to include (and probably save) some kind of random value. $\endgroup$
    – Maarten Bodewes
    Feb 15, 2016 at 0:53
  • $\begingroup$ Many MACs give away the secret key if the MAC is known and the key is reused, unless a cipher is used to hide its value. $\endgroup$
    – Demi
    Feb 15, 2016 at 0:58
  • $\begingroup$ As pg1989 explains, unkeyed PRPs can only exist for domains with at most 1 element. ​ ​ $\endgroup$
    – user991
    Feb 15, 2016 at 1:02
  • 1
    $\begingroup$ crypto.stackexchange.com/q/14338/991 ​ ​ $\endgroup$
    – user991
    Feb 15, 2016 at 1:16
  • 2
    $\begingroup$ You may be looking for one-way permutations. $\endgroup$
    – fkraiem
    Feb 15, 2016 at 4:55

2 Answers 2


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:

  1. 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
  2. You do not need such an object for what you want. Just use a normal secure MAC and it is safe.
  • $\begingroup$ Good, now my mind at least is back in track. I started to wonder myself if I was wrong footed and there were MAC algorithms without this property. Nicely in line with my initial comment, at least regarding the basics. $\endgroup$
    – Maarten Bodewes
    Feb 15, 2016 at 9:26

Well, no. For something to be a pseudorandom permutation on some domain $\mathcal{D}$, it must be the case that a p.p.t. adversary can't distinguish it from a randomly-chosen permutation on $\mathcal{D}$. If there is no key or if the key is public, the adversary can just make a bunch of encryption queries and check whether they have the same ciphertext as the public permutation's.

You also mention that the function should be "one-way" but also be a permutation, which is a bit confusing. What exactly are you trying to accomplish here?

EDIT: I am still a little bit confused by your question, but let me point you in a potentially useful direction. Page 2 of this paper discusses garbling gates for Yao's garbled circuits in a model where all parties have access to a fixed public random permutation. The table at the top of the page shows a couple different constructions that might do what you want.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.