---
# System prepended metadata

title: Cryptography 密碼學 L2

---

# Cryptography 密碼學 L2
###### tags: 'Cryptography' 
1. Encryption definition
   Perfect Secret Encryption
    *    Encryption Def:
         $M$ 明文空間: message space
         $C$ 密文空間: ciphertext space
         $K$ 金鑰空間: key space
    三個演算法:
    1. Gen 金鑰產生 : probabilistic algo. Gen($1^λ$) → k ∈ $K$
    3. Enc 加密    : probabilistic algo. $Enc_k$(m) → c ∈ $C$
    4. Dec 解密    : deterministic algo. $Enc_k$(c) = m ∈ $M$
    λ: security parameter, used to describe the encryption
    Correctness: Pr[$Dec_k$(c):=m : c ← $Enc_k$(m)] = 1 ( ≈ 1)
   
3. Notations
    - Distribution over K, dist(K) defined by running Gen and taking the output key
    - $K$: ransom variable denoting the value of the key output by Gen 
    - Pr[$K$ = k} : for all k ∈ $K$, denotes the prob the key output by Gen is equal to k
    - $M$: random variable denoting the message being encrypted
    - Pr[$M$ = m] : similarly, for all m ∈ $M$, denotes the prob the message take on the value m ∈ $M$
    - Fixing an encryption scheme π = (Gen, Enc, Dec) and dist over $M$ determines dist over the space of ciphertext $C$ given k ∈ $K$, m ∈ $M$
        $C$  ← $Enc_k$(m)
      
5. Notion example
   Example: An adversary(對手) $A$ knows the message is either"attack today" with 70% or "not attack" with 30%, so Pr[$M$ = A.T] = 0.7, Pr[$M$ = N.A] = 0.3
   Remark : K and M are assumed to be independent
7. Shift cipher
   k = {0,...,25} with Pr[K = k]= 1/26
   Given the following dist of $M$ 
   Pr[M = 'a'] = 0.7
   Pr[M = 'z'] = 0.3
   What is the prob that ciphertext is 'B'?
    *  either 'a'→'B' M = 'a' & K = 1   0.7 * 1/26
    *   or 'z'→'B'    M = 'z' & K = 2   0.3 * 1/26
    Pr[ C = 'B'] = Pr[ M = 'a' ^ K=1]+ Pr[M = 'Z' ^K=2] = 1/26
    
9. Intuition of security
    Adversary - know & unknown 
    * Known: - Pro distribution over $M$ 
             - The encryption scheme π = (Gen, Enc, Dec)
    * Unknown: the only known thing is the shared key
    Intuition: 
    A scheme π meets perfect secrecy s.t. observing the ciphertext c should have no effect on $A$'s knowledge of message was sent 
    => c is useless to get m, reveals nothing about m
11. Definition 1 of perfect secrecy
    Perfect secrecy:
    An encryption scheme π = (Gen, Enc, Dec) with message space $M$ is perfectly secret if for every prob. distribution over $M$, every message m ∈ $M$ and every ciphertext c ∈ $C$ for Pr[C = c] > 0 : Pr[ M = m ｜ C = c] = Pr [M = m] 
13. Intuition of Definition 1
    c 對於 m 完全沒幫助
15. Shift cipher meets Definition 1
    
