One-way function

In computer science , a one-way function is a mathematical function that is “easy” to calculate in terms of complexity theory , but “difficult” to reverse . In a broader sense, functions are also referred to in this way for which no reversal that can be practically carried out in a reasonable time is known.

A vivid example would be a classic paper phone book for a larger city: If you know the name, you can very quickly find the corresponding telephone number. However, if you only know the telephone number, it is very time-consuming to find the associated name.

One-way functions form the basis of asymmetric cryptosystems .

definition

A mathematical one-way function must have the following properties: ${\ displaystyle f}$

The computation of the function value for a given is "simple"; that is, there is an algorithm that calculates it in polynomial time. ${\ displaystyle y = f (x)}$ ${\ displaystyle x}$

Computing the inverse of the function, i.e. H. of an archetype to a given such that is difficult, i. In other words , there is no probabilistic algorithm that runs in polynomial time and outputs a prototype for the input image with a probability that is not negligible . More precisely, for each probabilistic algorithm with suitable input and output format: for each is at a sufficiently large for a random equally distributed from the selected probability smaller than that successfully inverse image of that: . ${\ displaystyle x}$ ${\ displaystyle y}$ ${\ displaystyle f (x) = y}$ ${\ displaystyle F}$
${\ displaystyle F}$ ${\ displaystyle c \ in \ mathbb {N}}$ ${\ displaystyle n \ in \ mathbb {N}}$ ${\ displaystyle \ {0.1 \} ^ {n}}$ ${\ displaystyle x}$ ${\ displaystyle n ^ {- c}}$ ${\ displaystyle F}$ ${\ displaystyle f (x)}$
${\ displaystyle \ forall c \ in \ mathbb {N}: \ exists n_ {0} \ in \ mathbb {N}: \ forall n \ geq n_ {0}: P_ {x \ in \ {0,1 \} ^ {n}} {\ big (} \, f (F (f (x))) = f (x) \, {\ big)} \, <\, n ^ {- c}}$

Problem of the existence of the one-way functions

It is not known if there are any functions that satisfy the one-way condition. Indeed, the proof of their existence would also mean the proof for P ≠ NP . Conversely, the existence of one-way functions does not follow from P ≠ NP: A probabilistic algorithm can also be used to reverse the function. So that the inversion is sufficiently inefficient, NP must also not be a subset of the complexity class BPP .

Applications

One-way functions are of particular interest for applications in cryptology. For such use yet another requirement is necessary but computationally: The complexity classes referred consider the respective worst case ( worst case ), the longest term of an algorithm. For the cryptographic application, the algorithm must also be inefficient in the average case.

A one-way function is used directly for passwords . These are often not saved directly, but as the output of a cryptographic hash function into which the password is entered (usually supplemented with salt ). The check when logging in is then not carried out by comparing the passwords in plain text, but rather the hash values. This means that an administrator or an unauthorized person with system access can never read the passwords of the users. He can only try out possible passwords with a program like Crack . A cryptographic hash function behaves like a one-way function, more precisely: there is no known way to efficiently calculate an input for a given output ( pre-image attack ).

In practice, functions are known that have so far adequately met the requirements of a one-way function. However, it has not yet been possible to prove whether it is really “difficult” to invert them. An example of such a function is the multiplication of two large prime numbers , since it is believed that prime factorization is a "difficult" problem. Another example is modular exponentiation and its inverse, the discrete logarithm .

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

A variant of the one -way functions are trapdoor one-way functions , also called trap door functions . These can only be efficiently reversed if you have certain additional information. Trap door functions are used in asymmetric encryption methods such as RSA . A metaphor for trapdoor functions is the function of a mailbox: anyone can post a letter. However, it is very difficult to get it out - unless you have the key.

Well-known one-way functions in the broader sense

The following functions are named as one-way functions in a broader sense, for which no efficient inversion is currently known:

the cryptographic hash functions like SHA-2
the multiplication of two prime numbers or two integers is easy, while the reverse, the prime factorization , is difficult
the computation of the nth power of an element of a finite group is easy with a suitable choice of the group, while finding an exponent by computing the discrete logarithm is complex

literature

Jonathan Katz, Yehuda Lindell: Introduction to Modern Cryptography: Principles and Protocols . Chapman & Hall / CRC, 2007.

Web links

K. Rüdiger Reischuk, Markus Hinkelmann: One-way functions. Beware of the trap - the way back is only for the initiated! . At www.imn.htwk-leipzig.de