Does there exist a universal one-way permutation? Leonid Levin constructed a universal one-way function, i.e. a function which is one-way as long as there exists at least one one-way function.
But my question is, does there exist a universal one-way permutation, i.e. a function which is a one-way permutation as long as there exists at least one one-way permutation?  Would a modification of Levin’s construction achieve this?
To the best of my knowledge, this is unknown. That is, Levin's construction is a one-way function but most certainly not a one-way permutation. I don't see any way in which it can be modified to make it a permutation, since the way it works is by running arbitrary machines and then amplifying. Since there is no efficient way of checking if something is a permutation by looking at the machine (to the best of my knowledge), I don't see how one could modify Levin's construction.
Of course, this is just a limitation of what we know, and it begs a very interesting research question. Does there exist a universal one-way permutation? Similar questions can be asked about other primitives as well. A good paper to read that has some relation to this question (for other primitives) is On Robust Combiners for Oblivious Transfer and other Primitives by Harnik et al.