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 PNPP \neq NP


  1. Peking University Introduction to Information Security Class

See Also

  1. Trapdoor One-way Function