What it means to prove crypto secure

Computing · Networks & Security · ages 23-24

Name ______________________ Date ____________

Which direction does the lesson's hardness reduction use?
- From a hard-problem solver to generating longer secret encryption keys
- From a deployed code audit to removing the original hardness assumption
- From a scheme adversary to a solver for the hard problem
In the lesson's chosen-plaintext game, what access does the adversary receive?
- The secret key and permission to decrypt the challenge ciphertext
- Encryption queries and a challenge on equal-length messages
- Decryption queries and a challenge on unequal-length messages
Security in the stated game requires every polynomial-time adversary to have negligible advantage as the security parameter grows.
Circle one: True False
A valid reduction converts any efficient, non-negligible game attack into an efficient solver that contradicts the hardness assumption. What follows?
- The deployed program has no bugs under any possible attack model
- The scheme is secure in that game if the assumption holds
- The hard problem becomes easy without using a scheme adversary
A reduction simulates an adversary's game. What must it justify about the simulation?
- Its views match the game, or differences are bounded in the proof
- Its views reveal the secret key, even though the game withholds it
- Its queries can be ignored whenever answering them takes extra work
An implementation leaks its key through execution timing. Its scheme proof does not model timing observations. Does this leak contradict the proved game claim?
- Yes; every scheme proof certifies every possible timing behaviour
- Yes; every security game automatically includes all implementation leaks
- No; the timing attack is outside the proof's stated model
At one security-parameter value, an adversary's success probability is 0.56. Using advantage = |success - 0.50|, what can this alone establish?
- Advantage is 0.12, which proves an asymptotic security failure
- Advantage is 0.06, without settling asymptotic negligibility
- Advantage is 0.56, which proves every efficient attack succeeds
A wrapper uses a polynomial-time adversary but takes exponential time in the security parameter. The assumption forbids efficient solvers. What is missing?
- An efficient solver; exponential wrapper time breaks that requirement
- A secret algorithm; publishing the method invalidates every reduction
- A stronger assumption that every solver succeeds on its first attempt

Answer key

For grown-ups. Fold this page away before handing over the rest.

What it means to prove crypto secure W1-mt_qPCwxkqYY2-s1

From a scheme adversary to a solver for the hard problem · The reduction builds a hard-problem solver that uses an adversary against the scheme.
Encryption queries and a challenge on equal-length messages · The adversary may request encryptions and submit equal-length challenge messages. It receives neither the key nor decryption access.
True · The definition quantifies over efficient adversaries and requires asymptotically negligible advantage.
The scheme is secure in that game if the assumption holds · If the assumption holds, the forbidden solver cannot exist. The reduction therefore rules out the specified attack within that game.
Its views match the game, or differences are bounded in the proof · The adversary's success guarantee applies to its stated game. A different simulated view does not automatically inherit that guarantee.
No; the timing attack is outside the proof's stated model · The implementation is unsafe against this timing attack, but the narrower claim proved without timing observations need not be false.
Advantage is 0.06, without settling asymptotic negligibility · |0.56 - 0.50| = 0.06. Negligibility concerns behaviour as the parameter grows, not a result at one value.
An efficient solver; exponential wrapper time breaks that requirement · An exponential-time solver does not contradict an assumption that rules out efficient solvers.