Introduction

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.

Compute vs. Invert

Below you can experience the asymmetry of a one-way function firsthand. The function is f(x) = x2x^{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">Compute f(x) = x² mod n</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">Compute →</button>
    </div>
    <div class="result" id="fwdResult">f(x) = ?</div>
    <div class="sub" id="fwdSub"></div>
  </div>

  <div class="panel">
    <h3 class="panel-title">Invert: find x given f(x)</h3>
    <div class="row">
      <label>f(x) = <input id="yIn" type="number" min="0" max="9999" value="" placeholder="run compute first" /></label>
      <label>n <input id="nIn2" type="number" min="2" max="9999" value="97" /></label>
      <button id="invertBtn" type="button">Brute Force ⟳</button>
    </div>
    <div class="result" id="invResult">x = ?</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// One-way function demo: f(x) = x^2 mod n
// Forward direction: instant (one multiplication).
// Inverse direction: brute-force scan 0..n-1 — O(n) steps.
// At real cryptographic sizes (n ~ 2^2048) this is completely infeasible.

function compute() {
  const x = parseInt(document.getElementById('xIn').value, 10);
  const n = parseInt(document.getElementById('nIn').value, 10);
  if (isNaN(x) || isNaN(n) || n < 2 || x < 0) {
    document.getElementById('fwdResult').textContent = 'Invalid input';
    document.getElementById('fwdResult').className = 'result err';
    return;
  }
  const y = (x * x) % n;
  document.getElementById('fwdResult').textContent = 'f(' + x + ') = ' + y;
  document.getElementById('fwdResult').className = 'result';
  document.getElementById('fwdSub').textContent =
    fmt('%x%² = %v% ≡ %y% (mod %n%)  — 1 step', { x: x, v: x * x, y: y, n: n });
  // pre-fill the inversion panel
  document.getElementById('yIn').value = y;
  document.getElementById('nIn2').value = n;
  document.getElementById('invResult').textContent = 'x = ?';
  document.getElementById('invResult').className = 'result';
  document.getElementById('invSub').textContent = '';
  document.getElementById('progBar').style.width = '0%';
}

function invert() {
  const y = parseInt(document.getElementById('yIn').value, 10);
  const n = parseInt(document.getElementById('nIn2').value, 10);
  if (isNaN(y) || isNaN(n) || n < 2 || y < 0 || y >= n) {
    document.getElementById('invResult').textContent = 'Invalid input (need 0 ≤ f(x) < n)';
    document.getElementById('invResult').className = 'result err';
    return;
  }
  let found = null;
  let steps = 0;
  for (let candidate = 0; candidate < n; candidate++) {
    steps++;
    if ((candidate * candidate) % n === y) {
      found = candidate;
      break;
    }
  }
  const bar = document.getElementById('progBar');
  bar.style.width = (steps / n * 100).toFixed(1) + '%';

  if (found !== null) {
    document.getElementById('invResult').textContent = 'x = ' + found;
    document.getElementById('invResult').className = 'result';
    document.getElementById('invSub').textContent =
      fmt('Found after %steps% of %n% candidates scanned.  (%found%² mod %n% = %y%)', { steps: steps, n: n, found: found, y: y });
    console.log(fmt('Inversion: found x=%found% after %steps% steps, n=%n%', { found: found, steps: steps, n: n }));
  } else {
    document.getElementById('invResult').textContent = 'No pre-image found';
    document.getElementById('invResult').className = 'result err';
    document.getElementById('invSub').textContent =
      fmt('%y% is not a quadratic residue mod %n%. Scanned all %n% candidates.', { y: y, n: n });
    console.log(fmt('Inversion: no pre-image for y=%y% mod %n%', { y: y, n: n }));
  }
}

document.getElementById('computeBtn').addEventListener('click', compute);
document.getElementById('invertBtn').addEventListener('click', invert);
// run once on load to populate the forward result
compute();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/one-way-functions/Content licensed under CC BY-NC 4.0.