uplinks:: Cryptographic Primitives
tags:: #lang/en #type/term

One-way Function

• A one-way function is an invertible function that is easy to compute, but whose inverse is difficult to compute.
• Intuitively, a function is difficult to compute if any algorithm that attempts to compute the inverse in a “reasonable” amount of time will almost certainly fail.
• It is still not known whether one-way functions exist.
• Proof of the existence of one-way functions would simultaneously solve the P versus NP Problem.
  • Their existence would prove that $P \neq NP$

References

1. Peking University Introduction to Information Security Class

See Also

1. Trapdoor One-way Function