Cryptographic Security Definitions and Proof by Reduction
A scheme is secure when a precisely stated game leaves every efficient adversary a negligible advantage. Security is then proved by reduction: an adversary that wins the game is turned into an algorithm for a problem assumed hard, so breaking the scheme would break the assumption.
What a learner can do afterwards
- State a security game, name the adversary's powers, and say what advantage means in it
- Sketch a reduction from an adversary against a scheme to an assumed-hard problem
- Say what a proof of security does not promise about a deployed implementation
1 · Read
A scheme is called secure when a precisely stated game leaves every efficient adversary with only a negligible advantage. The game names exactly what the adversary may do, and the advantage says how much better than guessing they can do.
Security is proved by reduction. You show that any adversary who wins the game could be turned into an algorithm for a problem everyone assumes is hard. So breaking the scheme would break the assumption, which is taken to be out of reach.
To sketch a reduction, start from an adversary against your scheme and wrap it: feed it the game it expects, answer its moves, and translate its winning answer into a solution for the hard problem. The wrapper turns an attack into an algorithm.
A proof promises nothing about the deployed implementation. Bugs in the code, leaked secrets, and sloppy running of the system all sit outside what the game models.
State the game, bound the advantage, reduce attacks to a hard problem, and remember the proof covers the scheme, not the deployment.
2 · Watch
Take it off screen
Where it sits
Learn first
This opens up
Nothing builds on it yet.
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.