Search tools and guides ⌘K
VI · Cryptographic foundations

One-way functions

What it is

f(x) is easy to compute, f⁻¹(y) is computationally infeasible. The conjectural foundation of all asymmetric crypto.

Where it lives

Hash functions, password verification, every digital signature scheme.

The key insight

No one has proven they exist (P ≠ NP would imply it). The whole field operates on the assumption.

More in Cryptographic foundations
Discrete log Given g and gˣ mod p, find x. Believed hard for primes ~2048-bit; very… Birthday attack Finding any collision in an n-bit hash takes ~2^(n/2) operations, not … AEAD Authenticated Encryption with Associated Data. One operation provides …
Across the foundations
VII P vs NP Computational complexity VII NP-completeness Computational complexity VII Approximation algorithms Computational complexity VII Reductions Computational complexity VIII Central Limit Theorem Statistics & inference VIII Hypothesis testing & p-values Statistics & inference VIII Confidence intervals Statistics & inference VIII Power & sample size Statistics & inference
← All foundations