Cryptography筆記7 - Semantic Security

Shannon定義的secure cipher

簡單來說:給予一個ciphertext，完全無法得知任何plaintext的資訊。
不過shannon的定義太嚴謹，因為要求任意兩個message m0 m1被random key 加密後產生c的機率分布要一樣，這個需要跟message一樣長度的key length才行，實務上不能用。

如果loose Shannon的定義，使用computationally indistinguishable的機率分布 的話，即便兩個機率分布可能非常不一樣，一個普通的inefficient attacker無法破解。

Semantic Security

我們在把上面的定義loose一點，把任意兩個message 改成attacker能得到的message pair，這樣實務上就能符合此定義。

A 就是statistical test或是adversery，用比較loose的定義實際上是說明以下:

以下的討論都先限制attacker只能拿到一個ciphertext:

假設某個adversary A (statistical test algorithm A)，對某個challenger (cipher)提出挑戰，想要break cipher，A送出兩個 長度一樣的message m0, m1，challenger加密後丟給A，A要決定這是m0還是m1的ciphertext:

我們定義W0為實際是m0，但是A認為是m1，W1為實際是m1, 且A認為是m1的事件。

Semantic Advantage就是要觀察A對m0和m1的猜想機率是否有顯著的偏差? 越趨近於零越沒偏差，亦即A無法break cipher。

Semantically Insecure Example

有了semantic secure的定義，來看反例。
假設某efficient algorithm A可以把cipher text的LSB找出來plain text，則此cipher是否semantically secure? 否!

注意m0和m1的LSB都由A掌控了，根據semantic secure定義，Advantage應該要是可忽略的值，Adv = |Pr( W0 ) - Pr( W1 )|
= |0 - 1| = 1

由於A知道m0和m1的LSB，而且他也有能力從cipher text推導出plain text的LSB，所以Pr(W0) = 0，Pr(W1) = 1

這是相當大的advantage，換句話說這個cipher被break了。

one-time pad是semantically secure，事實上他是perferct securacy。