--- title: "Cryptographic Security Definitions and Proof by Reduction" description: "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 s" canonical: https://lightmysky.com/learn/computing/cryptographic-security-definitions-and-proof-by-reduction-mt_qPCwxkqYY2 source: https://lightmysky.com/learn/computing/cryptographic-security-definitions-and-proof-by-reduction-mt_qPCwxkqYY2.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # 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. Subject: Computing · Area: Networks & Security · Ages 23 to 24 Page: https://lightmysky.com/learn/computing/cryptographic-security-definitions-and-proof-by-reduction-mt_qPCwxkqYY2 ## Ready when they can - 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 ## Lesson: What it means to prove crypto secure 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. *(drawing: The game specifies the adversary's access and what counts as winning.)* 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. *(drawing: The hard-problem solver uses the hypothetical scheme adversary.)* **Example.** 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. **Recap.** 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.* ## Practice 8 questions on this page, each with its working shown. ## Optional connections - [Public-Key Cryptography and Key Exchange](https://lightmysky.com/learn/computing/public-key-cryptography-and-key-exchange-mt_AHCtrer4eh) - [Symmetric Encryption and What a Cipher Promises](https://lightmysky.com/learn/computing/symmetric-encryption-and-what-a-cipher-promises-mt_egJQEiFWZA) - [Reductions: Solving One Problem by Turning It into Another](https://lightmysky.com/learn/computing/reductions-solving-one-problem-by-turning-it-into-another-mt_PAwby3ZyAr)