Cryptographic Security Definitions and Proof by Reduction · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

What it means to prove crypto secure

Computing · Networks & Security · ages 23-24
Name ______________________   Date ____________

  1. What does a reduction turn an attack into?

    • A faster computer
    • A longer secret key
    • An algorithm for an assumed-hard problem

  2. In a security game, what must you name?

    • The brand of computer used
    • The adversary's powers and what winning means
    • The name of the programmer

  3. A secure scheme leaves every efficient adversary with negligible advantage.

    Circle one:   True   False

  4. Breaking the scheme would break the assumption. What follows?

    • The assumption becomes easy at once
    • The scheme is as safe as the assumption is hard
    • The scheme needs no keys

  5. Sketch step one of a reduction. Where do you begin?

    • Take an adversary that wins the game against the scheme
    • Assume no adversary will ever try
    • Change the hard problem first

  6. The proof holds, yet the app leaks secrets through a bug. Does that contradict the proof?

    • Yes, proofs cover all bugs
    • Yes, the game models every deployment
    • No, the proof never promised the implementation was correct

  7. A vendor claims the proof means their code has no bugs. What is wrong?

    • Proofs make code run faster
    • The proof covers the scheme in the game model, not the deployed code
    • Games remove the need for keys

  8. An adversary wins with large advantage. What does the reduction give you?

    • An efficient algorithm for the supposedly hard problem
    • A proof that the problem is easy for everyone
    • A new game with no adversary
LightMySky · lightmysky.comW1-mt_qPCwxkqYY2-s1

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

  1. An algorithm for an assumed-hard problem · Reduction wraps the attacker into a solver.
  2. The adversary's powers and what winning means · The game pins down powers and winning exactly.
  3. True · That is the definition of secure in the game.
  4. The scheme is as safe as the assumption is hard · Safety flows from the hardness you assumed.
  5. Take an adversary that wins the game against the scheme · Reductions start from a hypothetical winner.
  6. No, the proof never promised the implementation was correct · The game models the scheme, not the deployed code.
  7. The proof covers the scheme in the game model, not the deployed code · No game result certifies an implementation.
  8. An efficient algorithm for the supposedly hard problem · A real winner converts into a real solver.
Worksheet · LightMySky