A cryptographer proves that breaking scheme S is at least as hard as factoring 2048-bit integers. A colleague says this means S is unconditionally secure. What is the flaw?
Think about your answer, then reveal below.
Model answer: The proof shows security relative to the factoring assumption — if factoring is hard, then S is secure. But no one has proven factoring is hard (this would imply P != NP). The reduction means S is secure under the factoring assumption, which is a widely believed but unproven conjecture. If someone discovers an efficient factoring algorithm, both the assumption and every scheme reduced to it collapse simultaneously.
This is the fundamental limitation of computational cryptography. All security proofs are conditional on unproven assumptions. The cryptographic community gains confidence in assumptions through decades of failed attacks by experts, but this is empirical evidence, not mathematical proof. Unconditional security (information-theoretic) requires impractically long keys (Shannon's theorem).
Question 2 Multiple Choice
The Decisional Diffie-Hellman (DDH) assumption states that (g^a, g^b, g^{ab}) is computationally indistinguishable from (g^a, g^b, g^c) for random a, b, c. Why is DDH a stronger assumption than CDH?
ADDH requires larger group elements than CDH
BDDH asks adversaries to distinguish (a harder task than computing), but DDH implies CDH: if you can compute g^{ab} from (g^a, g^b), you can certainly distinguish (g^a, g^b, g^{ab}) from (g^a, g^b, g^c) by computing g^{ab} and comparing. So DDH being hard is a stronger claim than CDH being hard
CDDH applies to elliptic curves while CDH applies to integers
DCDH is a special case of DDH where a = b
In the hierarchy: DDH ⇒ CDH ⇒ DLP. Breaking DLP (computing a from g^a) solves CDH (compute (g^b)^a); breaking CDH solves DDH (compute g^{ab} and compare). Each implication is one-directional — no one has shown the reverse. DDH is actually false in some groups where CDH appears hard (e.g., groups with bilinear pairings), which is why pairing-based cryptography uses different assumptions.
Question 3 Short Answer
A security proof via reduction shows: 'If adversary A breaks scheme S with advantage epsilon in time t, then algorithm B solves hard problem H with advantage epsilon/q in time t + O(q).' What do epsilon and the 'tightness' of the reduction tell us?
Think about your answer, then reveal below.
Model answer: Epsilon is the adversary's advantage in breaking the scheme. The reduction's tightness — the ratio between the adversary's advantage against S and the resulting advantage against H — determines how the scheme's concrete security relates to the assumed hardness of H. A tight reduction (epsilon vs epsilon, or close) means the scheme is about as hard to break as the underlying problem. A loose reduction (epsilon vs epsilon/q for large q) means the scheme could be significantly easier to break than the problem, requiring larger security parameters to compensate.
Tightness matters for concrete parameter selection. If the reduction loses a factor of 2^30, you need to add 30 bits to your security parameter. Loose reductions are a major practical concern: a scheme with a security proof but a loose reduction may need impractically large keys. Much research aims to tighten reductions or find schemes with inherently tight proofs.
Question 4 True / False
If P = NP, all commonly used computational hardness assumptions in cryptography would collapse.
TTrue
FFalse
Answer: True
All standard assumptions (factoring, RSA, CDH, DDH, LWE) assert that certain problems in NP cannot be solved in polynomial time. If P = NP, every NP problem is solvable in polynomial time, so every such assumption is false. This would break all public-key cryptography, most symmetric cryptography beyond one-time pads, and all zero-knowledge proofs. The belief that P != NP is therefore a meta-assumption underlying the entire field. However, some cryptographic primitives might survive specific collapses — if factoring becomes easy but LWE remains hard, lattice-based cryptography would survive even as RSA falls.
Question 5 Multiple Choice
Cryptographers prefer to base schemes on the weakest possible assumption. Why?
AWeaker assumptions require less computation to verify
BA scheme based on a weaker assumption is secure under more scenarios — if the stronger assumption turns out to be false but the weaker one holds, the scheme survives. Fewer assumptions mean fewer potential points of failure
CWeaker assumptions always lead to more efficient schemes
DRegulatory standards require the use of minimal assumptions
If scheme A is based on DDH and scheme B is based on CDH, then B is secure in strictly more worlds — it survives even if DDH is broken (as long as CDH holds). Since DDH failing does not imply CDH failing, B is more robust. The ideal is to base cryptography on the weakest assumptions that allow the desired functionality. However, there are tradeoffs: weaker assumptions sometimes lead to less efficient constructions, so practical schemes balance assumption strength against performance.