But how can we use such problems in public-key cryptography? The basic idea, as first formulated in [49], is to use so-called trapdoor or one-way functions. These are invertible mathematical functions that are easy to compute but computationally hard to invert. The easy part can be used for encrypting. The way to design a public-key cryptosystem is now to find a special piece of information, the private key, which makes the computation of the inverse function easy for the owner of the private key.