# Using data compression and randomization to build an unconditionally secure short key cipher(使用資料壓縮和隨機化來建構無條件安全的短密鑰)
[Paper Website](https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9965864&tag=1)
##### tag: `short key cipher` `data cimpression` `data randmization` `unconditionally secure`

## 研究目的
:::info
在密鑰長度小於加密訊息長度的情況下打造絕對安全的密鑰，也就是在一個有無限計算資源的對手只要他沒有獲取密鑰那他就不能獲得加密資料的任何資訊。
:::

## 貢獻
:::success
提出了一種新的對稱加密方法，先對原始資料進行資料壓縮和隨機化的轉換，使得轉換後的訊息的長度和最小熵的差值是一個小常數，然後再應用一種基於熵安全的加密方法，使得密鑰長度只取決於所需的安全等級，而不取決於訊息的熵或長度。

這種加密方法使用了Shannon coding和其修剪版本(trimmed Shannon coding)作為資料壓縮的工具，並使用了一種隨機化的前綴碼來增加資料的熵。作者證明了這種加密方法的熵安全性和不可區分性，並可估計密鑰長度。

原先想讓密碼是無條件安全的有很多的限制，例如一次性密碼要求密鑰的長度至少要跟原始資料的長度一樣，而本論文提出了將短訊息也能擁有無條件安全的密鑰。
:::

## 介紹
:::info
### 熵(Entropy):
密鑰的熵可以用來衡量密碼的強度，通常用來指密鑰的隨機性或是不可預測性，熵值越高代表密鑰的的隨機性越大，安全性越高。
而本論文中所使用的基於熵安全的加密方法使得密鑰長度只取決於所需要的安全等級，而不取決於訊息的熵或長度。

### 不可區分性(Indistinguishability):
這是一種加密系統的性質，表示即使敵人有無限的計算資源也無法區分加密訊息和一個隨機變數。
這是設計加密系統和協議時的一個基本原則，有助於確保系統在各種情境下都能保持足夠的安全性。

### 最小Entropy(min-entropy):
這是一種確認資料機率分布不確定性的方式，被用來表示攻擊者成功猜中密鑰的最壞情況，強密鑰通常有最高的min-entropy，這意味著即使在最差的情況下，攻擊者也難以成功預測密鑰。

### Huffman coding & Shannon coding & Trimmed Shannon Coding的差別
#### Huffman coding
* 為一種自適應編碼，可在編碼過程中動態地調整編碼表，無須預先知道符號的機率，適合用在不知道機率分布的情形。
* 使用二元樹來編碼。
* 為無失真編碼，在解碼時不會發生資訊損失，每個符號都有唯一的編碼。

#### Shannon coding
* 為一種前瞻性編碼，在編碼前就需知道所有符號的機率。
* 使用資料中每個符號出現的機率來編碼，機率越高的符號其編碼越短，以實現整體編碼的平均長度最小化。
* 為無失真編碼，在解碼時不會發生資訊損失，每個符號都有唯一的編碼。

#### Trimmed Shannon Coding
* Trimmed Shannon Code修剪了機率較低的符號，即對機率較低的符號不分配編碼。
* 減少了編碼表的大小進而提高了編碼的效率與節省儲存空間
* 降低平均編碼長度
* 為失真編碼，因為發生機率低的符號沒有分配編碼

:::

## 研究方法
:::success
### 資料壓縮的方法:
作者使用到了兩種資料壓縮技術，Shannon coding 和 Trimmed Shannon coding
會使用到資料壓縮的目的為將原始資料轉為一種更緊湊的形式，這樣即使在密鑰長度較短的情況下也能有效的維持或是增強加密資料的安全性。

Shannon coding:
為一種無失真編碼，可將資料壓縮到較短的表示形式，同時保持資料的完整性。
基於資料的機率分布的編碼方法，透過將資料映射到較短的編碼來實現資料壓縮。這種方法可以使原始資料的機率分布更接近均勻分布，從而增加資訊的entropy，

### 研究方法(第三章):
1.Entropy和密鑰長度:
密鑰長度取決於entropy
k >= n - h_min + 2log(1/ϵ) + 2
介紹這個公式

2.兩步加密方法:
首先將原始資料隨機編碼為另一個新的資料，使新的資料的entropy接近最大值，再將新的資料使用entropy-secure的加密方式進行加密。這樣可以使得密鑰的長度與原始資料的entropy無關，同時保證加密的安全性

3.資料壓縮和隨機化技術:
使用Shannon coding和Trimmed Shannon coding來實現最優編碼，從而使得新資料的entropy接近最大值

### 畫個資料加密的流程圖
:::

## 結論(第四章):
:::info
所提出的加密方法對於任何最小entropy都是有用的，但對於[3]只在k = n - hmin + 2 log(1/ε) 小於 n的情況下是有用的，其中n是加密資料的長度，k是密鑰的長度。

討論了為什麼要選擇使用Trimmed Shannon coding(因為Trimmed Shannon coding的編碼長度與最小編碼長度之間的差不超過2)，而那些未被使用的Huffman coding和 Shannon-Fano coding也可能在未知資料機率分布或其他情況下是有用的(這段應該不算是這篇論文的重點，像是沒把研究做完的缺點而已)
:::