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$
• Worst-case adversary:
  • Computationally unbounded
  • Might know Gen, Enc, Dec but doesnt now the key or their internal randomness
  • But can see the ciphertext
• 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

Shannon’s perfect secrecy definition:

• A-posteriori = A-priori
• seeing the ciphertext should provide absolutely no additional information about the plaintext message.
• $\forall \mathcal{M}\forall m\in \mathrm{Supp}(\mathcal{M}),\forall c\in \mathrm{Supp}(\mathcal{C})$,

$$\mathrm{Pr}\left[\mathcal{M}=m\mid Enc\left({}_{a,},\mathcal{M}\right)=c\right]=\mathrm{Pr}[\mathcal{M}=m]$$

• Achievable with One-time pad as example
  • but reusing OTP doesnot achieve perfect indistinguishability therefore, not perfect secrecy
  • theorem For any perfectly secure encyption scheme, $|K|\ge |M|$

Perfect indistinguishability definition:

• A Turing Test
• $\forall M\forall m,m^{\prime }\in \text{Supp}(M)$
• With 2 worlds:
  • $k\leftarrow K,c=E(k,m)$
  • $k\leftarrow K,c^{\prime }=E(k,m^{\prime })$
• Adversary is a distinguisher (sees $c$ and tries to guess which world it is in)
• Perfect indistinguishability means adversary has no way of knowing which world he is in
• $\forall \mathcal{M}\forall m,m^{\prime }\in \mathrm{Supp}(\mathcal{M}),\forall c\in \mathrm{Supp}(\mathcal{C})$,

$$\mathrm{Pr}\left[Enc\left({}_{n{n}^{\prime }},m\right)=c\right]=\mathrm{Pr}\left[Enc\left({}_{n{n}^{\prime }},m^{\prime }\right)=c\right]=\alpha$$

Perfect secrecy and Indistnguishibility

• theorem An encryption scheme (Gen, Enc, Dec) satisfies perfect seccy IFF it satisfies perfect indisguishability
• Proof: use conditional probability

Caesar cipher

• The Caesar Cipher is a private-key encryption schemeclaim

One-time pad

Turing’s code

• Known-plaintext attack