4
$\begingroup$

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?

$\endgroup$
6
+50
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.