One-way function

A function $f:X\to Y$ is a one-way function, if $f$ is ‘easy’ to compute for all $x\in X$, but $f^{-1} is ‘hard’ or ‘infeasible’ to compute.

• ‘easy’: solved in polynomial time as function of input length
• ‘infeasible’: effort to solve grows faster than polynomial time as a function of input size