nLab cryptography

Redirected from "encryption".
Contents

Contents

Idea

In computer science, cryptography is the art and science of securing communication and information through the use of mathematical techniques.

Its roots trace back to ancient civilizations where secret codes were employed to protect sensitive messages. The earliest known use of cryptography is attributed to the ancient Egyptians, who used hieroglyphs to inscribe messages on monuments in a way that could only be understood by those with the knowledge of the secret key.

Today, cryptography relies on a wide variety of mathematical topics. Here is a non-exhaustive list of fields and topics that are particularly relevant to cryptography:

  • Number Theory (modular arithmetic, prime numbers, and group theory in the context of modular arithmetic)

  • Abstract Algebra (groups, rings, and fields such as Galois fields)

  • Algebraic Geometry (elliptic curve cryptography and algebraic varieties over finite fields)

  • Combinatorics (combinatorial designs and error-correcting codes)

  • Probability Theory (randomized algorithms in cryptography and probability distributions relevant to cryptographic protocols

  • Graph Theory (graph-based cryptographic algorithms and network flow algorithms in the context of network security)

  • Topology (algebraic topology and homological algebra)

  • Logic (in the context of formal verification and proof systems)

  • Complex Analysis (analytic number theory)

  • Functional Analysis (for signal processing and cryptographic protocols)

Symmetric and asymmetric cryptography

There are two fundamental types of cryptography: symmetric and asymmetric. Symmetric cryptography involves the use of a single secret key kk for both encryption E k:MCE_k:M \to C and decryption D k:CMD_k:C \to M. This key must be securely shared between the communicating parties.

Bob Channel Alice m E k(m) D k(E k(m))=m \begin{array}{ccccc} \mathsf{Bob} &\longrightarrow& \mathsf{Channel} & \longrightarrow &\mathsf{Alice}\\ m & \longrightarrow & E_k(m) & \longrightarrow & D_{k}(E_k(m)) = m \end{array}

On the other hand, asymmetric cryptography uses a pair of keys – a public key kk for encryption E k:MCE_k:M \to C and a private key kk' for decryption D k:CMD_{k'}:C \to M. This asymmetric key pair allows for secure communication without the need for a shared secret, offering enhanced security in various scenarios.

Bob Channel Alice m E k(m) D k(E k(m))=m \begin{array}{ccccc} \mathsf{Bob} &\longrightarrow& \mathsf{Channel} & \longrightarrow &\mathsf{Alice}\\ m & \longrightarrow & E_k(m) & \longrightarrow & D_{k'}(E_k(m)) = m \end{array}

In practice, Alice would generate both keys kk' and kk and would send the public key kk to Bob.

Security and attacks

Security in cryptography is a constant battle against potential attacks. Common attacks include brute force, where an attacker systematically tries all possible keys, and cryptanalysis, which involves exploiting vulnerabilities in the cryptographic algorithm.

Modern cryptographic systems aim to withstand these attacks, often relying on the complexity of mathematical problems, such as factoring large numbers or solving discrete logarithms, to ensure security.

Complexity classes

Complexity classes play a pivotal role in cryptography, providing a framework to analyze the efficiency and security of cryptographic algorithms.

The study of computational complexity helps assess the computational resources required to break a cryptographic scheme, distinguishing between feasible and infeasible attacks.

Invertibility principle

In cryptography, the concept of invertibility is essential for ensuring secure decryption. When plaintext undergoes encryption through the encryption algorithm E k:MCE_k:M \to C, the efficacy of the system depends on the ease of decryption for authorized users and the complexity it imposes on unauthorized attempts.

Bijections (or isomorphisms) E:MCE:M \to C whose inverses D=E 1:CMD = E^{-1}:C \to M are hard to compute provide practical examples of this principle. Such bijections (E,D)(E,D) establish a one-to-one relationship between plaintext MM and ciphertext CC, enabling straightforward decryption given suitable information (constituting the potential private key kk) while posing a significant challenge for unauthorized attempts.

Mathematically, we could imagine that Alice and Bob have access to a groupoid 𝒢\mathcal{G} and a category 𝒞\mathcal{C}, respectively, such that 𝒞\mathcal{C} is embedded in 𝒢\mathcal{G} via an inclusion functor.

𝒞𝒢 \mathcal{C} \hookrightarrow \mathcal{G}

The security of a cryptosystem would then rely on the difficulty of reconstructing this inclusion using an algorithmic completion procedure.

These mathematical principles form the foundation for secure cryptosystems, ensuring that only authorized users can successfully decrypt and access sensitive information.

Remark

Note that there is flexibility in considering weaker notions of isomorphisms, especially if Alice can employ these weaker isomorphisms effectively in the decryption of the message mm from the data D k(E k(m))D_{k'}(E_k(m)).

D k(E k(m))m D_{k'}(E_k(m)) \leftrightarrows m

In category theory, examples of these weaker notions can be derived from higher category theory. This includes concepts such as adjoint equivalences, algebras, coalgebras, and retractions.

Post-quantum cryptography

With the advent of quantum computers, there is growing concern about the potential threat they pose to existing cryptographic systems. Post-quantum cryptography is an evolving field that explores algorithms resistant to quantum attacks.

Researchers are developing cryptographic schemes that rely on mathematical problems difficult for both classical and quantum computers to solve, ensuring the continued security of communication in the post-quantum era.

Homomorphic cryptography

Homomorphic cryptography takes a unique approach by allowing the processing of operations \square on encrypted data without decrypting it first.

D(E(m 1)E(m 2))=m 1m 2 D(E(m_1) \square E(m_2)) = m_1 \square m_2

This field aims to preserve privacy while still enabling meaningful computations on sensitive information.

Fully homomorphic cryptography, a subset of homomorphic cryptography, extends this concept to support arbitrary computations on encrypted data, opening new possibilities for secure and privacy-preserving data processing in various applications, including cloud computing and data analytics.

References

General

probabilistic:

  • Shafi Goldwasser, Silvio Micali, Probabilistic encryption, Journal of Computer and System Sciences 28:2 (1984) 270-299

Verified software

On verified software for cryptography:

On type theory for verified cryptography:

  • Cédric Fournet, Karthikeyan Bhargavan, Andrew D. Gordon, Cryptographic Verification by Typing for a Sample Protocol Implementation, In: Aldini A., Gorrieri R. (eds) Foundations of Security Analysis and Design VI. FOSAD 2011. Lecture Notes in Computer Science, vol 6858. Springer (2011) (doi:10.1007/978-3-642-23082-0_3)

  • Cédric Fournet, Markulf Kohlweiss, Pierre-Yves Strub, Modular code-based cryptographic verification, CCS ‘11: Proceedings of the 18th ACM conference on Computer and communications securityOctober 2011 Pages 341–350 (doi:10.1145/2046707.2046746)

On homotopy type theory for verified cryptography:

Last revised on January 25, 2024 at 08:13:29. See the history of this page for a list of all contributions to it.