One-way function

In computer science, a one-way function is a mathematical function that is computationally " easy " predictable, but " hard " to invert. In an expanded sense, functions are called so, which so far is not known in a timely practically executable reversal.

One-way functions are the basis of many encryption methods in cryptology.

Definition

A mathematical one-way function must have the following properties:

• The calculation of the function value is " simple", that is, there exists an algorithm that can compute it in polynomial time.

• The calculation of any inverse function to a known value, ie a so, however, is " hard ", ie there is no "fast " algorithm for this problem. " Quick " means here a probabilistic algorithm that runs in polynomial time.

A clear comparison offers a classic paper phone book of a large city: If you know the name, then you will find very quickly the corresponding phone number. However, you only know the phone number, so it is very expensive to find the corresponding name.

Problem of the existence of one-way functions

It is not known whether there are features that meet the conditions of one-way. In fact, the proof of their existence would simultaneously have the proof of P ≠ NP result. Conversely, does not follow from P ≠ NP, the existence of one-way functions: To reverse the function of a probabilistic algorithm may be used. Thus, the reversal is thus sufficiently inefficient, in addition NP may not be included (real or fake ) in the complexity class BPP.

Applications

One-way functions are of particular interest for applications in cryptology. For such an application is computationally still another requirement necessary: ​​the complexity classes mentioned in each case consider the worst case ( worst case), the longest running time of an algorithm. For the cryptographic application, the runtime needs to be inefficient in the average case ( average case ).

Direct application of a one-way function, there are at passwords. These are often not stored readable, but encrypted using a one-way function. The test at login is then not by comparing the password in plain text, but the cipher. This can never read the passwords of the user an administrator or with an unauthorized system access. He can try possible passwords if need be with a program like crack.

In practice, known functions which meet the requirements of a one-way function so far enough. So far it has not been demonstrated, however, the proof, if it is really " hard " to invert it. An example of such a function is the multiplication of two large prime numbers, since we assume that a prime factorization is a "difficult " problem. Another example is the modular exponentiation, and its inverse, the discrete logarithm.

One-way functions with trapdoor ( trapdoor one-way functions )

A variant of one-way functions are trapdoor one-way functions, also called trapdoor functions. This can only be reversed efficiently when one has some additional information. Trapdoor functions can be used in asymmetric encryption algorithm such as RSA. An apt metaphor for trapdoor functions is the function of a mailbox: Anyone can throw a letter. Getting out, however, is very difficult - unless you are in possession of the key.

Known one-way functions in a broad sense

As a one-way functions in a broad sense the following functions are called, which is known to have no efficient inversion.

• The cryptographic hash functions such as MD5 or SHA1
• The multiplication of two prime numbers or of two integers is easy, while the reversal, the prime factorization is hard
• The calculation of the n- th power of an element of a finite group is simple, with a suitable choice of the group, while the discovery of an exponent is complicated by calculating the discrete logarithm