One-Way Functions

Every time you log in to a website, your password is not stored in plain text — it is run through a function whose output reveals nothing useful about its input. Every time you send an encrypted message, a key is derived using operations that your adversary cannot feasibly undo. The invisible foundation of all of this is the idea of a one-way function.

A one-way function is a function f that is:

• Easy to compute: given any input x, you can calculate f(x) in polynomial time.
• Hard to invert: given only f(x), recovering any pre-image x' such that f(x') = f(x) is computationally infeasible — it would take more time than the age of the universe for realistic input sizes.

The striking thing about one-way functions is that we do not know whether they exist. Their existence has never been proven. The best candidates — squaring modulo a large composite, evaluating a cryptographic hash, multiplying large primes — are widely believed to be one-way, but no proof is in sight.

This is not a minor technicality. If one-way functions do not exist, then P = NP, and modern cryptography collapses entirely. Their existence would imply P ≠ NP, one of the deepest open problems in mathematics. In other words, the security of the internet rests on a conjecture we cannot prove.

See P vs NP for why separating these two complexity classes is so profound.

Below you can experience the asymmetry of a one-way function firsthand. The function is f(x) = $x^{2}$ mod n, where n is a fixed modulus. Computing it is instantaneous. Finding x from f(x) by brute force takes exponentially more work.

<div class="owf-wrap">
  <div class="panel">
    <h3 class="panel-title">{{title_forward}}</h3>
    <div class="row">
      <label>x <input id="xIn" type="number" min="0" max="9999" value="42" /></label>
      <label>n <input id="nIn" type="number" min="2" max="9999" value="97" /></label>
      <button id="computeBtn" type="button">{{btn_compute}}</button>
    </div>
    <div class="result" id="fwdResult">{{fwd_init}}</div>
    <div class="sub" id="fwdSub"></div>
  </div>

  <div class="panel">
    <h3 class="panel-title">{{title_invert}}</h3>
    <div class="row">
      <label>f(x) = <input id="yIn" type="number" min="0" max="9999" value="" placeholder="{{placeholder_run_first}}" /></label>
      <label>n <input id="nIn2" type="number" min="2" max="9999" value="97" /></label>
      <button id="invertBtn" type="button">{{btn_brute}}</button>
    </div>
    <div class="result" id="invResult">{{inv_init}}</div>
    <div class="sub" id="invSub"></div>
    <div class="bar-wrap"><div class="bar" id="progBar"></div></div>
  </div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #1a1a2e; }
.owf-wrap { display: flex; flex-direction: column; gap: .9rem; padding: .4rem; }
.panel { background: #f0f4f8; border-radius: 10px; padding: .9rem 1rem; border: 1px solid #d0dae4; }
.panel-title { margin: 0 0 .65rem; font-size: .95rem; font-weight: 700; color: #1d3557; }
.row { display: flex; flex-wrap: wrap; gap: .5rem; align-items: flex-end; margin-bottom: .6rem; }
label { font-size: .85rem; color: #333; display: flex; flex-direction: column; gap: .2rem; }
input[type=number] { font: 600 15px ui-monospace, monospace; padding: .35rem .5rem;
  border: 1px solid #adb1b8; border-radius: 6px; width: 88px; }
button { font: 600 14px system-ui; padding: .42rem .9rem; background: #1d3557; color: #fff;
  border: none; border-radius: 7px; cursor: pointer; white-space: nowrap; }
button:hover { background: #274577; }
.result { font: 700 1.15rem ui-monospace, monospace; margin: .3rem 0 .1rem; color: #0a7d33; min-height: 1.6em; }
.result.err { color: #c92f3c; }
.sub { font-size: .82rem; color: #555; min-height: 1.2em; }
.bar-wrap { height: 6px; background: #d0dae4; border-radius: 3px; margin-top: .5rem; overflow: hidden; }
.bar { height: 100%; width: 0%; background: #e63946; border-radius: 3px; transition: width .08s linear; }

// Code not found

Notice how computing f(x) always finishes in a single step, while inverting requires the computer to scan every candidate value from 0 to n−1 until it finds one whose square matches. Double n and the search roughly doubles; a realistic modulus of 2048 bits would require more steps than atoms in the observable universe.

One-way functions occupy a strange position in complexity theory: everyone uses them, but no one can prove they exist.

Status: open conjecture — their existence has never been proven, and no proof is expected soon. The best we can say is:

• If P = NP, one-way functions cannot exist. Any function computable in polynomial time would also be invertible in polynomial time (just search all pre-images efficiently). This would break all of modern cryptography.
• If one-way functions exist, then P ≠ NP. So their existence is a strictly stronger assumption than P ≠ NP — it would imply the separation but not conversely.
• The belief gap: the research community is nearly certain that one-way functions exist, yet this belief is based on decades of failed attempts to break candidates, not on proof.

Beyond their own existence, one-way functions are the minimal cryptographic primitive. From them alone (using constructions by Håstad, Impagliazzo, Levin, and Luby, 1999) you can build:

• Pseudorandom generators (PRGs) — stretch a short secret seed into a long stream indistinguishable from random.
• Pseudorandom functions (PRFs) — keyed functions that look random to anyone without the key.
• Message authentication codes (MACs) and symmetric encryption.

Public-key cryptography (like RSA) needs the stronger notion of a trapdoor one-way function — a one-way function that becomes easy to invert when you know a secret trapdoor. Even trapdoor functions are unproven; RSA's hardness rests on the assumption that integer factoring is hard.

The hierarchy runs: one-way functions → PRGs → PRFs → symmetric crypto → (with trapdoor) → public-key crypto. Every layer rests on an unproven assumption.

One-way functions are not a theoretical curiosity — they are the engineering reality behind every secure system in use today:

• Password hashing: when you set a password, the server stores H(password) using a function like bcrypt or Argon2. An attacker who steals the database cannot reverse the hash to recover your password.
• Digital signatures: signing a document requires a trapdoor one-way function. Anyone can verify the signature (the easy direction); only the holder of the private key can create one (the hard direction).
• Key exchange (Diffie-Hellman): two parties agree on a shared secret over a public channel by exploiting the hardness of the discrete logarithm — a conjectured one-way function.
• Pseudorandom number generation: cryptographically secure random-number generators use one-way functions to stretch a small seed into an unpredictable stream used for session keys, nonces, and IVs.
• Commitment schemes: a one-way function lets you commit to a value (show f(x)) without revealing it, and later prove you knew x — the basis of zero-knowledge proofs.

Every time your browser shows a padlock, every time a signature is verified, every time a password login works — a one-way function is doing the work.

One-way functions are remarkable precisely because of what we do not know about them. We build entire civilizations of digital trust on the assumption that they exist — yet no mathematician has ever proven it.

Their existence is entangled with P vs NP: if someone proved P = NP tomorrow, every password, every signature, every encrypted message would be breakable in polynomial time. Conversely, a proof that one-way functions exist would be the deepest result in complexity theory since the field began.

Until that day, we live on the comfortable side of a conjecture — trusting, with very good reason but no proof, that squaring a number modulo a billion-digit composite is genuinely irreversible. The padlock in your browser is a daily act of faith in an unproven theorem.