## 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.

• Case 1 (the trivial case): For some function $\ell$ it holds that $D_i=\bitset^{\ell(|i|)}$ and $I=\bitset^*$. This case is clearly equivalent to the case of a single function (as discussed above).
• Case 2 (the hybrid case): Again $D_i=\bitset^{\ell(|i|)}$, but here $I\subset\bitset^*$ is an arbitrary sampleable set. One major issue in this case is that here the potential invertor gets the index $i\in I$ but not the coins used to sample $i$. Using such OWP may be more involved than using Case 1; see Certifying Permutations: Noninteractive Zero-Knowledge Based on Any Trapdoor Permutation (by M. Bellare and M. Yung, J. of Crypto., Vol. 9, pages 149-166, 1996).
• Case 3 (the natural/flexible case): The general case is that both $D_i\subset\bitset^{\ell(|i|)}$ and $I\subset\bitset^*$ are sampleable [see Volume 1, Sec 2.4.4]. Two special cases were considered for trapdoor permuations, but analogue definitions are nature also in case of OWP.
• Case 3.1: Enhanced security (see Volume 2, Apdx C.1). Here the potential invertor the coins used to sample the domain element for which it should provide a preimage.
• Case 3.2: Dense domain (see Haitner's thesis and paper in TCC'05). That is, $D_i$ contains a noticeable fraction of $\bitset^{\ell(|i|)}$, but deciding membership in $D_i$ may not be easy.
[November 2005.]

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