Skip to main content
Engineering LibreTexts

2: The Basics of Provable Security

  • Page ID
    7326
  • Until very recently, cryptography seemed doomed to be a cat-and-mouse game. Someone would come up with a way to encrypt, someone else would find a way to break the encryption, and this process would repeat again and again. Crypto-enthusiast Edgar Allen Poe wrote in 1840,

    “Human ingenuity cannot concoct a cypher which human ingenuity cannot resolve.”

    With the benefit of hindsight, we can now see that Poe’s sentiment is not true. Modern cryptography is full of schemes that we can prove are secure in a very specific sense.

    If we wish to prove things about security, we must be very precise about what exactly we mean by “security.” Our study revolves around formal security definitions. In this chapter, we will learn how write, understand, and interpret the meaning of a security definition; how to prove security using the technique of hybrids; and how to demonstrate insecurity by showing an attack violating a security definition.

    • 2.1: Reasoning about Information Hiding via Code Libraries
      All of the security definitions in this course are defined using a common methodology, which is based on familiar concepts from programming. The main idea is to formally define the “allowed” usage of a cryptographic scheme through a programmatic interface, and to define what information is hidden in terms of two implementations of that interface (libraries).
    • 2.2: One-Time Secrecy for Encryption
      We now have all the technical tools needed to revisit the security of one-time pad.
    • 2.3: Hybrid Proofs of Security
    • 2.4: Demonstrating Insecurity with Attacks
      We have seen an example of proving the security of a construction. To show that a construction is insecure, we demonstrate an attack. An attack means a counterexample to the definition of security. Since we define security in terms of two interchangeable libraries, an attack is a distinguisher (calling program) that behaves as differently as possible when linked to the two libraries.
    • Exercises