# Variations of Cryptosystem
> 資料來源：NCKU 李南逸教授之**密碼學**課程－密碼學應用 2。

## Homomorphic Encryption

:::info
本人專題題目，故不詳細記錄。
:::

### Concept

舉個例子：在公司上班薪水很高，老闆今天想幫大家加薪，但他不想讓每個人知道其他人加了多少薪，一般的加解密系統沒辦法「還原亂碼」，而同態加密可以。
> 缺點是複雜度高、效率不佳。

### Simple Homomorphic Encryption Example

應用情境：投票機制。

### Homomorphic Encryption Algorithms
> 老師不熟 GM、Benaloh。
注意：ElGamal 是乘法同態，老師寫錯。

- 分「加法同態」及「乘法同態」。
> 若符合其中一個，稱「**半**同態加密」；都符合，則稱「**全**同態加密」。
- 右邊那串例子是 RSA，為乘法同態加密。

### ElGamal Scheme

#### Key Generation

#### Encryption

#### Decryption

#### Multiplicative Homomorphic

### Paillier Scheme
> 可參照 [Intel 的 Intel Paillier Cryptosystem Library](https://github.com/intel/pailliercryptolib_python)。
其有提到關於金鑰長度：For increased security, typically the key length is at least 1024 bits, but recommendation is 2048 bits or larger.

>深入查詢，現今主要流行 1024-bit 的金鑰長度，但自從 2009 年編號為 RSA-768（768 bits, 232 digits）數被成功分解後，普遍會建議將金鑰長度設置到 2048-bit 以上。

#### Key Generation

#### Encryption / Decryption

#### Proof

#### Additive Homomorphic

## Threshold Cryptosystem

### Threshold Cryptosystem (2, 3)

1. Alice 建立訊息
2. Alice 加密
- Alice 使用門檻加密法將訊息加密。
- 此加密過程會將加密結果分成多個密鑰分享（Decrypt Share），並分發給多個成員（Bob、Carol 和 Dave）。
3. Bob, Carol, Dave
- 這三位成員各自獲得一份密鑰分享，稱為 Decrypt Share。
- 即使他們個別持有自己的密鑰分享，但自己無法解密訊息。
4. Threshold Decrypt
- 當有至少兩個成員（如 Bob 和 Carol）提供他們的 Decrypt Share 時，門檻解密機制可以被觸發，並使用這兩個 Shares 來成功解密訊息。

### Shamir Secret Sharing Scheme (Lagrange Interpolation)

基於拉格朗日插值多項式的數學原理。

允許將一個秘密（如密鑰）拆分成若干個部分，並分配給不同的成員。
當足夠多的成員（至少門檻數）共同合作時，則可以恢復這個秘密。

#### Secret Sharing Algorithm
- `s`：即秘密。
- `n`：將密鑰拆分成 n 份。

#### Reconstruction Algorithm

#### (t, n) Secret Sharing Scheme
- `t`：閾值，至少需要 t 位成員才能重建秘密。
- `n`：將密鑰拆分成 n 份。

Shamir 使用一個次數為 $t−1$ 的隨機多項式（即圖中 $l(X)$）來隱藏這個秘密（$s$）。並將不同的 $X$ 值代入多項式 $l(X)$，計算出對應的 $s_i$ 值（即密鑰份額），並將這些 $(X,s_i)$ 的獨特 pairs 分配給不同的成員。

當有至少 $t$ 個成員合作時，就能使用拉格朗日插值多項式（代入使 $l(0)=s$）來重建這個秘密。

### ElGamal Threshold Cryptosystem

#### (t+1, n) threshold cryptosystem

### Laih-Harn Generalized Threshold Cryptosystem

#### Initialization

#### Trusted Center

#### Encryption
$C = M^e(mod\ N)$。

#### Decryption

## Proxy Re-Encryption (PRE)
- 代理重加密（簡稱PRE）目的是將「原本加密方（Delegator）透過加密方的密鑰所加密」的密文 $𝐶_a$，經由第三方代理服務，將密文轉換成「由解密方的密鑰加密」的密文 $𝐶_b$。
- 例如**雲端儲存**、**分享資料**的服務，經由 PRE 這樣的加密系統，能更有效率的在一對多、多對多的情況下進行訊息的分享。
- 對於同一個訊息，加密方只需要產生一次密文，再經由 Proxy 和重加密密鑰 𝑟𝑘，就能對不同人產生個別的秘密副本，解密方只需要用自己的密鑰便能解密密文。
- Proxy 在轉換密文的過程中，只會接觸到「密文」跟「重加密」。
- 密鑰，明文訊息跟解密密鑰並不會暴露給第三方。

### Architecture
如下圖架構：
- Proxy 即雲端，其存有**密文**。
- $A\rightarrow B$ 是隨機值。
- 步驟：
1. $C_A$
2. $rk_{A\rightarrow B}$
3. $C_B$
- Bob 那邊：$m = Dec(sk_B, C_B)$。

### Properties
- **Directionality**
- 如果 Proxy 只能利用 𝑟𝑘 將 $𝐶_a$ 轉成 $𝐶_b$，就是 unidirectional，反之則為 bidirectional。
- **Number of Hops**
- 如果 Proxy 能透過不同的 $𝑟𝑘_{a→?}$ 將 $𝐶_a$ 轉換成對應的 $𝐶_?$，則稱為 multi-hop / multi-use，否則稱為 single-hop / single-use。
- **Interactivity**
- 如果解密方的密鑰不需參與重加密密鑰的產生過程，則稱為 non-interactive ，否則為interactive。

### BBS98 Scheme

### CTR2 Scheme
> 基於 ECC。


## 補充