Public-key Cryptography: Theory and Practice

C.3. One-way Functions and the Complexity Class UP

Any public-key encryption behaves like a one-way function, easy to compute but difficult to invert.

Definition C.1.

Let Σ be an alphabet (a finite set of symbols). One may assume, without loss of generality, that Σ = {0, 1}. Let Σ* denote the set of all strings over Σ. A function f : Σ* → Σ* is called a one-way function, if it satisfies the following properties. f must be injective, that is, for every β the inverse f–1(β), if existent, is unique. For some real constant k > 0, we have |α|1/k ≤ |f(α)| ≤ |α|k for all . (Here, |α| denotes the length of a string .) f can be computed in deterministic ...