display | more...

(Computer Science, Cryptography, Computational Complexity:)
An invertible (i.e. one-to-one and onto) function f is called "one-way" iff there exist efficient (say, polynomial time, or randomised polynomial time) algorithms for computing f-1(x), but no efficient algorithms for computing f(x).

NO ONE-WAY FUNCTIONS ARE KNOWN! Factorisation is thought to be a one-way function. We certainly know how to multiply in polynomial time; no polynomial algorithms for finding a prime factor of a number is known, not even if the number is known to be a multiple of exactly 2 primes. Discrete logarithms are also thought to be one-way functions (even when the group and base for exponentiation are known). Additionally, it is known that discrete logarithms are at least as hard to compute as factors: it is known how to use an oracle which computes discrete logarithms in order to factorise large numbers.

Nonetheless, one-way functions are the mainstay of modern public-key cryptography and related techniques. RSA is based on factorisation, as are many others; Diffie-Hellman on discrete logarithms (again, many more also). Without one-way functions, most of these techniques become useless.

But, given the sorry state of complexity analysis today (no non-trivial lower bounds are known for any general model of computation), it seems hard to imagine the day when we know that some function is one-way. A quantum computer can certainly solve both the above one-way functions -- but no quantum computers exist today. A polynomial algorithm for factorisation or discrete logarithms might exist. But it is scarcely conceivable given our current knowledge of algebra and number theory.

One-way functions remain something of an article of faith. Most (almost all?) cryptographers seem to believe the above two functions are safe for quite a few years... but predicting the future (either that they'll be cracked, or that they'll be proven safe) is always a risky business.

Today it seems that a world with one-way functions is more interesting than one without. I'd go with the one-way functions... but I'd be very careful where I go with them!

Related, but different, are trapdoor functions -- you might want to read about those, too.

Log in or register to write something here or to contact authors.