# 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