Practical OWP of the set of $k$-bit bitstrings for low $k$ Down to what $k$ and how can we devise a practical, public, efficiently computable One Way Permutation $P$ of the set $\{0,1\}^k$ of $k$-bit bitstrings, if possible without involving a trusted party for parameter setup ? Note: I want $P$ to be a permutation in the mathematical sense, and computationally hard to invert for some definition of that.



For values of $k$ starting at bout $2000$, we can use the assumed hardness of the Discrete Logarithm Problem (RSA also works if we trust a party to generate and publish an appropriate public key, and destroy any clue that could lead to factorization of the modulus).

For example, with the DLP, we find the smallest prime $p$ at least $\sqrt[3]{9}\,2^k$ such that $q=(p-1)/2$ is also prime, find the smallest $g$ at least $p/\pi$ such that $g^q\bmod p=1$, and define function $F$ over the set $\{1,2\dots q\}$ as $F(x)=\min\big(g^x\bmod p,p-(g^x\bmod p)\big)$. As far as we know, $F$ is an OWP over that set. We then use cycling to reduce $F$ to a permutation $P$ of $\{0,1\}^k$: we convert the input bitsring to integer, add one, apply $F$ and iterate (on average $\sqrt[3]{9}/2\approx1.04$ times) until the result is at most $2^k$, subtract one, convert back to bitstring.



Addition: I'll cowardly let the answer state its security claim. Informally, I'd be happy with a vague argument that more than $\min(2^n,2^{128})$ cycles of classical CPU are required for anything that should require more than $2^n$ evaluations in the forward direction, like finding a bitstring $x$ with the first $n$ bits of $P(x)$ all-zero (or other arbitrary $n$-bit value defined independently of the definition of $P$).

Motivation: I read that OWPs are more useful than OWFs. I wonder if that matters in practice. I reason that if we can't get $k$ down to say 256, we could as well use as a practical equivalent of a OWP a hash of $k$ bit (and same input size); it's most likely not a OWP, but it can't be computationally distinguished from that if the hash is secure.
Here is an outline of a system that would yield $k \approx 256$.

Let us select an elliptic curve (based on a prime field of size $N \approx 2^{256}$ with:


Is secure, and has twist security (that is, the discrete log problem on the curve and on its twist is infeasible)
Has a single point of order two (the $x=y=0$ point)
Both the curve, and its twist form a cyclic group (which is mostly a consequence of the previous two assumptions)


We'll select a generator of the curve $G$ and a generator of the twist $G^*$ (note: if you are basing this on Curve25519, then the conventional $g=9$ does not work, as that generates a prime-order subgroup, not the entire curve)

Then, if the order of the curve is $q$ and the order of the twist is $q^*$, then every value between 1 and $N-1$ can be represented as either (but not both):


The $x$ coordinate of a point $kG$, for some $1 \le k &lt; q/2$
The $x$ coordinate of a twisted point $kG^*$, for some $1 \le k &lt; q^*/2$


So, if we map the integers $k \in [1, q/2)$ to the $x$ coordinate of $kG$, and the integers $k \in [q/2, q/2 + q^*/2)$ to the $x$ coordinate of $(k - q/2 + 1)G^*$, I believe that gives a hard-to-invert permutation of the integers in the range $[1, N-1]$.  And, you can use the tricks you have listed to make that down into a slightly smaller range $[0, 2^k)$.

Do you see any obvious problems with this?