Foundations of Security
The foundations of security provide the rigorous mathematical underpinnings of cryptography: precise definitions of what security means, the hardness assumptions security rests on, and the reductions that prove schemes secure.
Definition
The foundations of security comprise the definitional frameworks, computational assumptions, and proof techniques used to specify security goals precisely and to demonstrate rigorously that cryptographic constructions achieve them.
Scope
This area covers the theory that makes cryptography a science rather than an art: formal security definitions and adversary models, computational hardness assumptions, the reduction-based methodology of provable security, and the central role of randomness and pseudorandomness. It addresses how 'secure' is defined and demonstrated. It excludes the concrete primitives and protocols that instantiate these ideas, which are treated in the cryptography-focused areas.
Sub-topics
Core questions
- What does it mean, formally, for a cryptographic scheme to be 'secure'?
- How are an adversary's powers and goals captured in a precise model?
- On what unproven but plausible hardness assumptions does security rest?
- How does a reduction prove that breaking a scheme would solve a hard problem?
- Why is randomness and pseudorandomness foundational to cryptography?
Key concepts
- security definitions
- adversary models
- semantic security and indistinguishability
- computational hardness assumptions
- reductions
- one-way functions
- pseudorandomness
- negligible probability
- computational vs information-theoretic security
Key theories
- Semantic security and indistinguishability
- Goldwasser and Micali defined encryption security as semantic security — a ciphertext reveals nothing computationally useful about the plaintext — shown equivalent to ciphertext indistinguishability, replacing vague intuitions with a precise, achievable goal.
- Provable security by reduction
- A scheme is proven secure by a reduction showing that any efficient adversary breaking it could be turned into an algorithm solving an assumed-hard problem; security is thus conditional on the assumption but rigorous.
Clinical relevance
The foundational viewpoint is why modern cryptography can be trusted: instead of hoping a scheme resists attack, designers prove that breaking it is as hard as a well-studied problem under a precisely stated adversary model. This methodology underlies the security claims of every standardized primitive and protocol, guides which schemes regulators and standards bodies approve, and explains why ad hoc, unproven designs are deprecated.
Evidence & guidelines
Provable-security analysis is now expected in cryptographic standardization (NIST competitions for AES, SHA-3, and post-quantum schemes all weighed security proofs and reductions). Machine-checked proofs (EasyCrypt) and standardized models (random-oracle, standard model) provide rigor, though debates persist about idealized assumptions. Constructions whose security rests only on heuristics are discouraged.
History
Cryptography became a rigorous science in the early 1980s when Goldwasser and Micali introduced probabilistic encryption and semantic security (1982-1984), giving the first precise definitions and proofs. Yao and Blum-Micali formalized pseudorandomness, and the reduction-based methodology spread through the 1980s and 1990s, consolidated in Goldreich's 'Foundations of Cryptography'. This definitional revolution distinguishes modern cryptography from earlier code-making.
Key figures
- Shafi Goldwasser
- Silvio Micali
- Oded Goldreich
- Andrew Yao
- Manuel Blum
Related topics
Seminal works
- goldwasser1984
- goldreich2001
- katz2020
Frequently asked questions
- What does 'provably secure' actually mean?
- It means there is a mathematical proof that breaking the scheme is at least as hard as solving some problem believed to be intractable, under a stated adversary model. It is not an absolute guarantee: security is conditional on the hardness assumption and the model being faithful to reality.
- Why rely on unproven hardness assumptions at all?
- Most useful cryptography cannot be proven secure unconditionally — doing so would resolve major open problems like P versus NP. Instead, security is reduced to a small set of long-studied problems (factoring, discrete log, lattices) whose difficulty is supported by decades of failed attacks.