skip to content

A product's safety rests on nobody inverting a one-way function cheaply, so what would a proof that P equals NP do to it?

level: seniorimportance: must knowfreq 52%

answer

  1. look at the attacker's task as a search
  2. confirming a guess is one forward step
  3. no hard-to-invert function could survive
  4. unconditional secrecy never assumed a budget
  5. the reverse implication does not hold

basics

~20 s

It would destroy the assumption. Inverting a function that is cheap to compute forward is a search whose check is one forward evaluation, so if that whole class of searches is polynomial, one-way functions do not exist and every scheme resting on computational hardness falls with them.

solid answer

~40 s

Take the design apart. The attacker holds an output and wants a preimage; the preimage is short, and confirming a candidate costs one forward evaluation, which is cheap by construction. That is a search with a polynomial check, so a constructive collapse makes inversion polynomial and one-way functions cannot exist. Everything built on them goes with them: key exchange, signatures, commitments, pseudorandom generators, password digests, proof-of-work. What survives is security that is information-theoretic rather than computational, which needs key material as large as the data. The sharper point for the review is the reverse direction: P differing from NP would **not** give you security, because hardness of that kind is worst case, while an attacker faces the random instances your system actually generates.

code

pseudocode · 10 lines
pseudocode
// f is cheap to evaluate forward; y is the value we must invert

verify(candidate):
    return f(candidate) == y          // one forward evaluation

attack(y):
    for each candidate x of length n:  // 2^n candidates today
        if verify(x):
            return x                   // a confirmed preimage
    return none

go deeper

for a junior

Remember the shape: an attacker guessing a secret can check a guess cheaply, because running the function forward is the easy direction. That is why the whole scheme lives or dies on the hard direction staying hard.

for a middle

Explain why inversion is a search with a polynomial check, and therefore why hard-to-invert functions cannot exist if that family of searches is easy. Name one primitive that falls and one that does not.

for a senior

In a review, challenge the reverse claim. Worst-case hardness is not security; ask which distribution the assumption is stated over and which single problem the design is betting on.

for a principal

Decide what your organisation actually owes this risk. A universal collapse has no product-level answer, so the budget belongs to assumption diversity, replaceability and an explicit secrecy lifetime for the data.

## Why inversion is a search with a cheap check The design says: a function is easy to evaluate forward and nobody can run it backwards within any budget that matters. Look at what an attacker actually has to do. They hold an output. They want any input mapping to it. That input is short — comparable in size to the output — and there is a free way to confirm a guess: evaluate the function forward once and compare. So inversion sits in exactly the family the open question is about, a search over short candidates with a fast test. That gives the implication in the direction that matters here. If every such search becomes polynomial, inversion becomes polynomial, and a function nobody can invert cheaply cannot exist. Stated the standard way round: **the existence of one-way functions implies that P and NP are different**. A proof of the collapse therefore refutes their existence as a corollary. ## What falls - **Key agreement over an open channel** — the eavesdropper's problem is a search with a cheap check. - **Digital signatures** — forging is the search for a value that passes the public verification test, which is fast by design. - **Commitments and zero-knowledge protocols** whose hiding or binding property rests on a computational assumption. - **Pseudorandom generators**, whose output is defined to be indistinguishable from random only against bounded adversaries. - **Password digests**, where the attacker's task is literally preimage search under a fast forward function. - **Proof-of-work schemes**, whose whole purpose is to make a search expensive while the check stays cheap. ## What does not fall Security that is **information-theoretic** rather than computational is untouched, because it never assumed any bound on the attacker's computation in the first place: a key as long as the message and used exactly once, threshold secret sharing with the right parameters, authentication with one-time key material. The catch is the reason it is rare in practice — it requires key material proportional to the data and distributed in advance, which is precisely the problem computational cryptography exists to solve. | Assumption | Fate under a practical collapse | |---|---| | One-way function, trapdoor permutation | Gone; inversion is polynomial | | Pseudorandomness against bounded adversaries | Gone; the adversary bound no longer bites | | Key as long as the message, used once | Unaffected; never depended on hardness | | Sharing that reveals nothing below the threshold | Unaffected; information-theoretic | ## The direction that actually catches candidates The interesting failure in a design review is not the doomsday direction, it is the reassuring one. Somebody writes 'breaking this is NP-hard, therefore it is secure'. Three things are wrong with that: 1. **Hardness of that kind is a worst-case claim.** It says some instances are hard. An attacker does not face a worst-case instance, they face the ones your key generator produces, and average-case hardness over that distribution is a separate and much stronger requirement. 2. **The assumptions actually used are not known to be complete for NP.** Integer factoring, discrete logarithms and the lattice problems underpinning newer constructions are all believed hard, and none is known to be among the hardest problems in NP. Their hardness is a conjecture of its own, not a corollary of the open question. 3. **A scheme needs more than a hard problem.** It needs the hardness to survive the specific way the problem is embedded — the key distribution, the padding, the protocol around it. Hard problems have been wrapped in broken schemes many times. So the honest summary of the relationship is asymmetric: a collapse would certainly destroy computational security, while a separation would not by itself establish it. ## How to answer in the review Say the risk is real but not the one to plan around. If the collapse happened constructively and with usable constants, this product would fail and so would nearly every other system whose safety is computational — there is no product-level mitigation for that, and a design document should not pretend to have one. Then redirect to the risks that are actually actionable: which single assumption is load-bearing here, how long the protected data must stay secret, and how hard it would be to swap the primitive if that one assumption fell to an ordinary algorithmic advance. That is the conversation worth having, and it is the one a reviewer is really asking for when they raise the question.

  • Would a non-constructive proof of the collapse change the risk picture immediately?
    Not operationally on day one, since no attack would exist yet. But the assumption would be known false, which is a different posture from unproven: a universal search procedure would then be guaranteed polynomial, with constants that make it useless for now, and any improvement in those constants becomes an attack. A reviewer should treat it as a dead assumption on a slow fuse.
  • Why is 'breaking our scheme is NP-hard' a weak security argument even today?
    Because hardness of that kind quantifies over the worst instance, while an attacker meets the instances the key generator produces. Security needs hardness on that distribution. Many problems are hard in the worst case and easy on average, so the reduction proves far less than it appears to.
  • Which schemes would still be secure, and why are they not used everywhere?
    Those whose security is information-theoretic: a key as long as the message used once, and sharing schemes that reveal nothing below their threshold. They assume nothing about the attacker's computation, so no complexity result touches them. They are rare because they need key material proportional to the data and delivered in advance, which is the very problem computational cryptography was invented to avoid.

saying these in an interview costs you the question

  • Thinks only public-key schemes would be affected
  • Says a separation of P from NP would prove the scheme secure
  • Treats worst-case hardness as hardness against a real attacker
  • Assumes the underlying assumptions are known to be NP-complete
  • Claims no scheme at all would survive a collapse
  • Proposes a product-level mitigation for a universal collapse