12/4/13

Trapdoor function.

A trapdoor function is a function that is easy to compute in one direction, yet believed to be difficult to compute in the opposite direction (finding its inverse) without special information, called the 'trapdoor'. Trapdoor functions are widely used in cryptography.

In mathematical terms, if f is a trapdoor function there exists some secret information y, such that given f(x) and y it is easy to compute x. Consider a padlock and its key. It is trivial to change the padlock from open to closed without using the key, by pushing the shackle into the lock mechanism. Opening the padlock easily, however, requires the key to be used. Here the key is the trapdoor.

An example of a simple mathematical trapdoor is '6895601 is the product of two prime numbers. What are those numbers?' A typical solution would be to try dividing 6895601 by several prime numbers until finding the answer. This is slow solution, which are rather unpractical for most needs.

However, if one is told that 1931 is part of the answer, one can find the answer by entering '6895601 / 1931' into any calculator. This example is not a sturdy trapdoor function--modern computers can guess all of the possible answers within a second--but this sample problem could be improved by using the product of two much larger primes.

Source: Wikipedia.

See also: One-way compression in Cryptography (it's not so related as it might seem at first).

No comments:

Post a Comment