Practical OWP of the set of $k$-bit bitstrings for low $k$
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?