Private-key cryptography

Definition:

• A triplet of algorithms (Gen, Enc, Dec), a message space $M$, and a key space K$,$ together is called a private-key encryption scheme if:
  1. The key-generation algorithm, Gen is a randomized algorithm that returns a key, $k\leftarrow \text{Gen}$, such that $k\in K$.
  2. The encryption algorithm, $\text{Enc}:K\times M\to \{0,1{\}}^{\ast }$ is an algorithm that takes as input a key $k\in K$ and a plain-text $m\in M$ (the message), and outputs a cipher-text $c={\text{Enc}}_k(m)\in \{0,1{\}}^{\ast }$
  3. The decryption algorithm, $K\times \{0,1{\}}^{\ast }\to M$ is an algorithm that takes as input a key $k\in K$ and a cipher-text $c\in \{0,1{\}}^{\ast }$, and output a plain-text $m\in M$.
  4. The scheme is correct; that is, decrypting a valid cipher-text should output the original plain text. Formally we require that for all $m\in M,k\in K,{\text{Dec}}_k({\text{Enc}}_k(m))=m$
• Consists of:
  • A triplet of al algorithms Gen, Enc, Dec

    • flowchart LR
        subgraph Alice
        direction LR
        msg1[Message]-->ENC
        end
        ENC --jizberisz--> DEC
        subgraph Bob
        direction LR
        DEC--> msg2[Message]
        end
        sk[SecretKey]
        sk --> ENC
        sk --> DEC
      

  • A message space $M$
  • A key space $K$

Algorithm triplet:

• Gen
  • Alice and Bob first need to meet in advance to generate and agree on a secret key $k\in K$
    • Secret keys are shared
  • A uses secret key to encrypte a message, becomes a cyber text,
  • A sends cyber message to B, B then decrypt using the agreed secret key
• Enc
  • Alice has a private message $m\in M$ for Bob, she sends $c={\text{Enc}}_k(m)$ over the insecure channel.
• Dec
  • Once Bob receives the cipher-text $c$, he decrypts it by running $m={\text{Dec}}_k(c)$ to read the original message

Caesar cipher

• The Caesar Cipher is a private-key encryption schemeclaim

One-time pad

Turing’s code

• Known-plaintext attack