A function is computable in polynomial time but hard to invert. Why is 'hard to invert' defined in terms of negligible probability of success across random inputs, rather than worst-case hardness?
Think about your answer, then reveal below.
Model answer: Worst-case hardness means some inputs are hard to invert, but an attacker might succeed on most inputs. Cryptographic security requires that inversion fails on almost all inputs — an adversary who can invert even a non-negligible fraction (say 1/n^c for any constant c) would break any scheme built on the OWF. The average-case hardness requirement (no PPT algorithm inverts with more than negligible probability over random inputs) ensures the function is reliably hard, not just occasionally hard.
This distinction is fundamental. NP-completeness guarantees worst-case hardness (some instances are hard), but cryptography needs average-case hardness (random instances are hard). An NP-hard problem might still have efficient algorithms that work on 99% of instances. OWFs require that no efficient algorithm works on more than a negligible fraction of inputs, which is a much stronger (and harder to prove) statement.
Question 2 Multiple Choice
If one-way functions exist, then P != NP. Does P != NP imply that one-way functions exist?
AYes — P != NP is exactly equivalent to the existence of OWFs
BNo — P != NP guarantees worst-case hardness, but OWFs require average-case hardness. It is believed that P != NP implies OWFs exist, but this has not been proven. There could be a world where P != NP but every efficiently computable function can be inverted on most inputs
CP != NP is irrelevant to one-way functions because they are defined over finite domains
DYes, but only for functions based on number-theoretic problems
OWF existence implies NP-hardness of inversion (so P != NP). But the reverse is open. P != NP means some decision problems have no efficient solution, but this is a worst-case statement. Constructing OWFs requires average-case hard problems — the gap between worst-case and average-case hardness is a major open question in complexity theory. Most complexity theorists believe OWFs exist (and most believe P != NP), but the implication from P != NP to OWFs is not proven.
Question 3 Multiple Choice
Integer multiplication (computing n = p * q from primes p, q) is a candidate one-way function. Why is it only a 'candidate' rather than a proven OWF?
ABecause multiplication is not actually in polynomial time
BBecause proving multiplication is one-way requires proving factoring has no polynomial-time algorithm, which would resolve P vs NP-type questions that remain open
CBecause quantum computers can factor integers, so multiplication is not one-way
DBecause multiplication is invertible using the extended Euclidean algorithm
We believe factoring is hard based on centuries of mathematical effort, but we cannot prove it. Proving any specific function is one-way would establish that P != NP (for certain structured variants), which is the most important open problem in theoretical computer science. Candidate OWFs are functions we believe are one-way based on empirical evidence (failed attack attempts) rather than proof. Quantum computers threaten factoring specifically, but that just means multiplication may not be one-way against quantum adversaries — the general concept of OWFs is not disproven.
Question 4 True / False
One-way functions are sufficient to construct pseudorandom generators, pseudorandom functions, MACs, commitment schemes, digital signatures, and CPA-secure symmetric encryption.
TTrue
FFalse
Answer: True
This is a central theorem of theoretical cryptography, established through a sequence of results by Goldreich, Goldwasser, Micali, Levin, Luby, Naor, Rompel, and others. OWFs → PRGs (Hastad-Impagliazzo-Levin-Luby) → PRFs (Goldreich-Goldwasser-Micali) → MACs → symmetric encryption. OWFs → universal one-way hash functions → signatures (Rompel). OWFs → commitment schemes → zero-knowledge proofs (for NP). The existence of OWFs is both necessary and sufficient for all of private-key cryptography and many public-key primitives.
Question 5 Short Answer
A one-way permutation is a one-way function that is also a bijection. Why is this additional structure useful?
Think about your answer, then reveal below.
Model answer: A one-way permutation (OWP) maps the domain onto itself bijectively, meaning every output has exactly one preimage. This eliminates ambiguity about what 'inverting' means and simplifies many constructions. The Goldreich-Levin theorem shows that any OWP can be converted into a pseudorandom generator by extracting a hard-core bit (a bit of the preimage that is unpredictable given the output). This PRG construction is cleaner and more efficient with OWPs than with general OWFs, which may have variable-size preimage sets.
OWPs are a stronger assumption than OWFs (every OWP is an OWF, but not conversely). However, many candidate OWFs (like RSA, which is a permutation on Z_n*) are naturally permutations. The OWP assumption simplifies theoretical constructions and gives tighter security proofs, which is why many foundational results in cryptography are first proven for OWPs and then generalized to OWFs.