Loading field map
Cryptography, as a subfield of theory of computation, has evolved through distinct paradigms that reflect its transition from an art to a rigorous science. The Classical Cryptography paradigm dominated until the mid-20th century, encompassing symmetric-key ciphers like substitution and transposition, which relied on heuristic security and manual cryptanalysis. This era lacked formal definitions, with secrecy often based on obscurity rather than mathematical principles, limiting its theoretical depth.
The Information-Theoretic Cryptography paradigm, established by Claude Shannon in the 1940s, introduced mathematical rigor by defining perfect secrecy through probability theory and information measures. Shannon's work characterized the one-time pad as unconditionally secure, but its practical key-length requirements spurred the field toward computational approaches. This paradigm laid the groundwork for formal security analysis but remained limited to ideal scenarios.
A major shift occurred with the Computational Cryptography paradigm, which integrated complexity theory to base security on computationally hard problems, such as factoring integers or computing discrete logarithms. This enabled practical symmetric-key systems with shorter keys and gave rise to the Public-Key Cryptography sub-paradigm, revolutionized by Diffie and Hellman in 1976. Public-key cryptography introduced trapdoor one-way functions for key exchange and digital signatures, fundamentally altering cryptographic design and enabling protocols like RSA and ElGamal.
The Provable Security framework became a cornerstone of theoretical cryptography, emphasizing reductions from cryptographic schemes to well-studied computational assumptions. This paradigm ensures that breaking a scheme implies solving a foundational problem, fostering rigorous analysis of encryption, signatures, and advanced protocols like zero-knowledge proofs and secure multi-party computation. It has shaped modern cryptographic standards and methodologies.
In recent decades, the Post-Quantum Cryptography paradigm has emerged to address quantum computing threats, focusing on algorithms secure against quantum attacks based on lattice problems, coding theory, and multivariate equations. This agenda continues the computational tradition while exploring new hardness assumptions, ensuring cryptography's adaptability. Together, these paradigms outline the historical spine of cryptography within theory of computation, each contributing durable technical agendas and schools of thought.