What methods do we know to construct a function $f:D\to D$

  1. with domain $D=[0,n)\cap\mathbb N$ (thus $n\in\mathbb N$ elements);
  2. demonstrably surjective (thus bijective since $D$ is finite);
  3. with definition requiring no trusted party for setup (e.g. an RSA modulus);
  4. computable by a deterministic algorithm running in time polynomial with $\log n$;
  5. conjectured not invertible in heuristic polynomial time on classical computers for random value to reach;
  6. practically secure w.r.t. the above with $n$ as small as possible, ideally at most $2^{512}$;
  7. as fast as possible, ideally competitive with a hash.

The closest I know is $f(x)=\left(g^x\bmod(n+1)\right)-1$ with $n+1$ a safe prime and $g$ a generator, which for $n$ in the thousands bits matches 1 to 5. But it's unsatisfactory from the standpoint of 6 and 7 compared to what symmetric cryptography achieves.

One possible application is as a building block for a demonstrably surjective hash function.



Browse other questions tagged or ask your own question.