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.