RSA Laboratories

2.3.2 What is a one-way function?

A one-way function is a mathematical function that is significantly easier to compute in one direction (the forward direction) than in the opposite direction (the inverse direction). It might be possible, for example, to compute the function in the forward direction in seconds but to compute its inverse could take months or years, if at all possible. A trapdoor one-way function is a one-way function for which the inverse direction is easy given a certain piece of information (the trapdoor), but difficult otherwise.

Public-key cryptosystems are based on (presumed) trapdoor one-way functions. The public key gives information about the particular instance of the function; the private key gives information about the trapdoor. Whoever knows the trapdoor can compute the function easily in both directions, but anyone lacking the trapdoor can only perform the function easily in the forward direction. The forward direction is used for encryption and signature verification; the inverse direction is used for decryption and signature generation.

In almost all public-key systems, the size of the key corresponds to the size of the inputs to the one-way function; the larger the key, the greater the difference between the efforts necessary to compute the function in the forward and inverse directions (for someone lacking the trapdoor). For a digital signature to be secure for years, for example, it is necessary to use a trapdoor one-way function with inputs large enough that someone without the trapdoor would need many years to compute the inverse function (that is, to generate a legitimate signature).

All practical public-key cryptosystems are based on functions that are believed to be one-way, but no function has been proven to be so. This means it is theoretically possible to discover algorithms that can compute the inverse direction easily without a trapdoor for some of the one-way functions; this development would render any cryptosystem based on these one-way functions insecure and useless. On the other hand, further research in theoretical computer science may result in concrete lower bounds on the difficulty of inverting certain functions; this would be a landmark event with significant positive ramifications for cryptography.

Top of the page