---
title: "Cryptographic Security Definitions and Proof by Reduction"
description: "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 algorit"
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-09-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 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.

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

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.

**Example.** 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.

**Tip.** 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.

**Recap.** State the game, bound the advantage, reduce attacks to a hard problem, and remember the proof covers the scheme, not the deployment.

## Practice

8 questions on this page, each with its working shown.

## Needs first

- [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)