## On Security Preserving Reductions: Revised Terminology

#### Webpage for a memo by Oded Goldreich

Many of the results in Modern Cryptography are actually
transformations of a basic computational phenomenon
(i.e., a basic primitive, tool or assumption)
to a more complex phenomenon
(i.e., a higher level primitive or application).
The transformation is explicit and is always accompanied by
an explicit reduction of the violation of the security of
the former phenomenon to the violation of the latter.
A key aspect is the efficiency of the reduction.
We discuss and slightly modify the hierarchy of reductions
originally suggested by Levin. The levels we suggest are:

- A reduction is
**strongly preserving**
if it guarantees $S'(n) > S(n)/poly(n)$,
where $S'$ denotes the security of the complex application
and $S$ denotes the security of the basic tool.
- A reduction is
**linearly-preserving**
if, for some constant $c\geq1$, it guarantees

$$S'(n) > \frac{S(n/c)}{poly(n)}$$
- A reduction is
**polynomially-preserving**
if, for some constants $c\geq1$ and $e>0$, it guarantees

$$S'(n) > \frac{(S(n/c))^e}{poly(n)}$$
- A reduction is
**weakly-preserving**
if, for some constants $c,d,e>0$, it guarantees

$$S'(n) > \frac{(S(c n^d))^e}{poly(n)}$$

**Material available on-line:**
the
original
memo, dating Jan. 2000.

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