On one-way permutations

A clarification by Oded Goldreich


Johan Hastad has noted that my textbook Foundations of Cryptography lacks a clear treatment of one-way permutations (OWP) per se. Following are a few comments.

I believe that there is no single right definition, but rather several different definitions, which unfortunately are used without distinction.

Firstly, there is the issue of a single infinite function (or permutation) versus an infinite collection of finite functions (or permutations). Typically, this distinction is always stated clearly.

For a single one-way function to be called a permutation, it should be 1-1 and length preserving [see Volume 1, Sec 3.4.1]. However, it is quite non-trivial to obtain appealing candidates for such OWP; see On Constructing 1-1 One-Way Functions (by O. Goldreich, L.A. Levin and N. Nisan, June 1995).

Turning to collections of permutations [see Volume 1, Sec 2.4.4 and 3.4.2], there are several versions. Referring to the basic formulation of $\{f_i:D_i\to D_i\}_{i\in I}$, one may consider the following cases.

[November 2005.]


Back to either Oded Goldreich's homepage. or general list of papers.