Cryptographic Security Definitions and Proof by Reduction
A security definition specifies a game and requires every efficient adversary to have negligible advantage as the security parameter grows. A reduction-based proof turns a hypothetical attack into a solver for an assumed-hard problem, accounting for running time and success loss. Its conclusion depends on the assumption and model.
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
An encryption game makes the cipher's promise precise. In this chosen-plaintext game, a challenger keeps a fresh secret key. The adversary may request encryptions and choose two equal-length messages. The challenger chooses a fair random bit b and encrypts message b using that key. The adversary guesses b. Encryption queries are allowed before and after the challenge; decryption queries are not.
Random guessing succeeds with probability 1/2. Here, advantage means the absolute difference between success probability and 1/2. Success probability 0.60 gives advantage 0.10. Other texts may use a convention twice this size, so state yours. A result at one security-parameter value does not determine whether advantage is negligible as that parameter grows.
The security parameter lambda controls key sizes and costs. Efficient adversaries may use randomness; their time is bounded by a constant times a fixed power of lambda. Here lambda^2 means lambda times lambda. Negligible advantage eventually falls below 1/p(lambda) for every positive polynomial p. For example, 1/lambda^2 is not negligible: it exceeds 1/lambda^3 for lambda > 1. Fixed positive advantage is not negligible. Security requires negligible advantage for every efficient adversary.
A reduction uses a hypothetical efficient adversary with non-negligible advantage to solve an assumed-hard problem. It receives an instance drawn from the assumption's distribution, simulates the adversary's game and uses its output to solve that instance. An efficient solver with non-negligible success would contradict the hardness assumption. The security conclusion depends on that assumption and game.
A simulation supplies the game's views and query replies or justifies differences in the proof. Count all wrapper work: polynomially many polynomial-time calls take polynomial time. A loss factor divides advantage in a success bound. If success is at least advantage/lambda^3 and advantage is 1/lambda^2, success is at least 1/lambda^5, still non-negligible. Exponential time or loss, such as a factor 2^lambda, may prevent the contradiction even if the wrapper sometimes solves an instance.
A proof covers its stated model, not every property of a deployed program. The implementation must realise the modeled scheme and meet its assumptions. A proof excluding timing leaks does not establish resistance to them. Code correctness, key generation and secret handling need their own checks. Proofs can cover implementation properties when those properties are explicitly modeled and proved.
State the game and advantage convention. Track the reduction's time and success loss. Security depends on the assumption, model and correct implementation.
Lesson, questions and flashcards on cryptographic security games and reductions written for this dataset.
2 · Watch
Take it off screen
Where it sits
Learn first
Nothing; this is a starting point.
Optional connections
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.