Cryptographic Hardness: OWF, PRG, and Why P=NP Breaks Everything

One mathematical result - P equals NP - would break HTTPS, Signal, and every bank simultaneously. Not through malicious code. Through a polynomial-time algorithm that inverts RSA. This is what cryptographic complexity means: the security of the internet is a theorem contingent on an unproven conjecture.

• NIST PQC 2024: CRYSTALS-Kyber and Dilithium on LWE - first standardized post-quantum algorithms with formal worst-case reduction
• Signal Protocol: X3DH and Double Ratchet on ECDH (discrete log assumption) - one billion users depending on one hardness assumption
• RSA-2048: security rests on the hardness of factoring a 617-digit number; best known classical algorithm GNFS requires 2^90 operations
• Shor's algorithm on quantum hardware: factors RSA-2048 in hours - the reason the industry is migrating to LWE-based schemes

One-Way Functions: The Load-Bearing Wall of Cryptography

All of modern cryptography stands on a single assumption: certain functions are easy to compute forward and hard to invert. This is not a theorem. It is a conjecture. P not equal to NP is necessary but not sufficient to guarantee one-way functions exist. If P equals NP, the conjecture collapses immediately - RSA, HTTPS, the Signal Protocol, AES in CTR mode - all broken in polynomial time. This is why P vs NP is not merely an academic question.

**One-Way Function (OWF)**: a function f: {0,1}* -> {0,1}* is one-way if: (1) f is computable in polynomial time; (2) for every probabilistic polynomial-time adversary A, the probability that A(1^n, f(x)) finds any preimage is negligible in n. 'Negligible' is precise: it means smaller than 1/p(n) for every polynomial p. A 1/poly(n) success probability is not negligible - cryptography needs failure probability that vanishes faster than any inverse polynomial.

**The Pessiland gap**: P not equal to NP means hard instances exist somewhere (worst-case). OWF requires hard instances to be everywhere in a distributional sense (average-case). The chasm between worst-case and average-case hardness is the central problem. Most NP-complete problems are easy on random instances - worst-case hardness does not translate to average-case hardness automatically. This is why P not equal to NP does not prove OWF exist.

Building the Hierarchy: PRG from OWF

In 1982, Blum and Micali proved that any OWF implies a pseudorandom generator. Yao proved the same thing independently the same year, via a different construction. This is more than a theoretical curiosity - it is the first link in a chain. OWF implies PRG implies PRF implies PRP implies symmetric encryption implies garbled circuits implies secure multiparty computation. Every layer is proven from the layer below. The chain's security ultimately reduces to the OWF assumption.

**PRG (Pseudorandom Generator)**: a deterministic polynomial-time algorithm G: {0,1}^n -> {0,1}^{l(n)} where l(n) > n (stretch). For every PPT distinguisher D: |Pr[D(G(U_n)) = 1] - Pr[D(U_{l(n)}) = 1]| < negl(n). Output is computationally indistinguishable from truly random. **Goldreich-Levin construction** (1989): extract a hard-core bit b(x) from a OWF - a single bit of x that is computationally unpredictable given f(x). Iterate this to build a PRG.

**Full primitive hierarchy**: OWF -> (Goldreich-Levin) -> PRG -> (GGM tree construction) -> PRF -> (Luby-Rackoff) -> PRP -> SKE -> (Yao) -> garbled circuits -> MPC. Public-key cryptography requires additionally: trapdoor OWP -> PKE. RSA is a trapdoor permutation: multiplying p and q is easy, inverting without the factorization is hard. Knowing the factorization provides the trapdoor for efficient inversion. Security of RSA reduces to the integer factoring assumption.

Post-Quantum Hardness: LWE, Lattices, and CRYSTALS

In 2024, NIST finalized the first post-quantum standards: CRYSTALS-Kyber for key encapsulation and CRYSTALS-Dilithium for signatures. Both rest on Learning With Errors (LWE): given a matrix A and vector b = As + e (mod q) where e is small noise, recover s. This problem is NP-hard in the worst case (Regev 2005). Regev also proved that average-case LWE is as hard as worst-case LWE via a quantum reduction. This is exceptionally rare: a cryptographic assumption with a formal worst-to-average reduction.

**LWE as a OWF**: f(s) = As + e is easy to compute and hard to invert - a one-way function candidate. Security parameters: dimension n around 1024, modulus q around 2^23, noise magnitude |e| much smaller than q. The underlying worst-case problem (Shortest Vector Problem, SVP) is NP-hard. CRYSTALS-Kyber on ARM: approximately 1 ms per operation, key size 1568 bytes - competitive with RSA-3072 in performance while resistant to Shor's algorithm.

**If P equals NP**: every OWF disappears. RSA: factoring is in NP, so it falls in polynomial time. Discrete log: same. SHA-256 preimage: in NP, so in P. LWE: solving a system of linear equations with small noise is in NP, so it falls. Every HTTPS session, every encrypted message, every banking transaction becomes retroactively breakable in polynomial time. P equals NP is not just a mathematical revolution - it ends computational privacy as currently implemented.

Related topics

Cryptographic complexity bridges abstract complexity theory and the practical security guarantees that underlie digital communication.

• NP and NP-completeness — Related topic
• Cryptographic protocols — Related topic

Итоги

• OWF: poly-time computable, negligible inversion probability for any PPT adversary; Impagliazzo Five Worlds maps the landscape from Algorithmica to Cryptomania
• PRG from OWF (Blum-Micali-Yao): hierarchy OWF->PRG->PRF->PRP->SKE->PKE via provable reductions - security chains to the OWF assumption
• P not equal to NP necessary but not sufficient: average-case hardness required; only LWE has a formal worst-to-average reduction (Regev 2005)
• Post-quantum: CRYSTALS-Kyber/Dilithium on LWE - NP-hard worst-case with quantum reduction; NIST standard 2024

Вопросы для размышления

• LWE has a formal worst-to-average hardness reduction - a stronger guarantee than integer factoring. Yet RSA with its weaker guarantee has been deployed at scale for decades longer. What does this tell us about the role of theoretical guarantees versus empirical trust in real-world security decisions?

Связанные уроки

• cplx-04 — NP - the class where cryptographic hardness assumptions live
• cplx-13 — Cryptographic protocols are built from the OWF/PRG hierarchy
• crypto-07-computational-complexity — Theoretical crypto foundations: same OWF/PRG from the cryptographer's perspective
• crypto-24-rsa-math — RSA: hardness = integer factoring - a concrete OWF assumption