Invertible Uniform "PseudoRandom" Function

Question

Perhaps this is better suited to a cryptography stack exchange, but I thought I'd try in mathematics in case this question is more obvious than I initially thought.

I'm looking for a function $~f:\{1,2,...,n\} \to \{1,2,...,n\}$ that satisfies the following criteria:

1. $f$ is invertible (and ideally, relatively easy to invert, computationally speaking).
2. $f$ has the appearance of mapping inputs in a uniform random manner to its range. That is, for $n = 5$ we might have $~f(1) = 4,~f(2) = 2,~f(3) = 1,~f(4) = 5,~f(5) = 3$. Of course, it just needs to appear random since the function must also be deterministically invertible. In fact, any sufficiently "messy" output would satisfy the needs for $f$.
3. $f$ should be defined for arbitrary $n$

Maybe this is a well documented problem and I just lack the proper vocabulary to do a quick search...

Thank you!

Answer 1

Many linear congruential PRNG can be used. Take $a$ with $\gcd(a,n)=1,\;$ i.e. $a^{-1} \bmod n$ exists and define $$f(x) = 1 + ((ax+b) \bmod n),\;$$ where $b$ is any integer. Then $f$ maps $[1,n]$ to $[1,n]$ and is invertible: from $y=f(x)$ you compute $$x=a^{-1}(y-1-b)\bmod n,$$ and if $x=0$ you should set $x=n,\,$ this comes from your unusal domain (normally $[0,n-1]$ is used).

Answer 2

I feel obliged to mention that the previous answer does not supply a cryptographically secure pseudorandom function.

It seems that the term you may be looking for is a strong Pseudorandom Permutation. Such a function meets all the criteria that you are looking for, including a much stronger definition of property 2. That is, a pseudorandom permutation cannot be distinguished from a truly random permutation by any probabilistic polynomial time adversary with probability at least $1 / \text{poly}(n)$, where $n$ is the security parameter used, for any polynomial $\text{poly}(n)$.

Note that the word "strong" in this context means easily invertible.