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

## Increase Efficiency

### On-line/Off-line Signature Scheme based on RSA
> 優點：速度快、效率佳；
缺點：**One-time**。

在線/離線簽名在需要快速生成簽名的環境中非常有用，無論是由於大量請求，還是因為執行簽名的設備計算能力不足。

#### Off-Line Computation
離線計算包括一次性密鑰方案的密鑰生成階段，其中包括生成密鑰對 $vk$ 和 $sk$ 並使用 RSA 簽署 $vk$。

因此，為了 bit-length 為 $n$ 的訊息進行簽名，簽名者首先執行以下步驟：
1. 選擇 $t = n + \lfloor{\log n}\rfloor + 1$ 個位長為 $l$ 的隨機秘密字串 $k_1, k_2, \dots, k_t$。
2. 計算 $u_i = H(k_i)$，其中 $1 \leq i \leq t$，並且 $H: \{0,1\}^* \to \{0,1\}^m$ 是一個 pre-image-resistant 的雜湊函數。

接著，$vk = (v_1, v_2, \dots, v_t)$ 和 $sk = (k_1, k_2, \dots, k_t)$。

現在，簽名者使用 RSA 簽名密鑰 $SK$ 簽署 $vk$，獲得 $\Sigma = H(vk)^S \mod N$，並且簽名者存儲 $vk$、$sk$ 和 $\Sigma$。

#### On-line Signing
為了對訊息 $m \in \{0,1\}^n$ 進行簽名，簽名者檢索已存儲的、預先計算的、未使用的三元組 $(vk, sk, \Sigma)$，並使用 $sk$ 來計算訊息 $m$ 的 one-time signature，具體步驟如下：

1. 計算 $c$，即訊息 $m$ 中 0 的數量的二進位表示。
2. 形成 bit-string $w = m \parallel c = (a_1, a_2, \dots, a_t)$。
3. 找出 $w$ 中 1 的位置 $i_1 < i_2 < \dots < i_u$，其中 $a_{i_j} = 1$，且 $1 \leq j \leq u$。
4. 設置 $s_j = k_{ij}$，其中 $1 \leq j \leq u$。

那麼，訊息 $m$ 的一次性簽名為 $\sigma = (s_1, s_2, \dots, s_u)$，而訊息 $m$ 的完整在線/離線簽名為 $(vk, \sigma, \Sigma)$。

#### Signature Verification
為了驗證 $(vk, \Sigma, \sigma)$ 是否是訊息 $m$ 的有效簽名，驗證者需要執行以下步驟：

1. 檢查 $\Sigma$ 是否是 $vk$ 的有效 RSA 簽名，與 $VK$ 相關，即 $\Sigma^e \equiv H(vk)(mod\ n)$。
2. 檢查 $\sigma$ 是否是 $m$ 的有效一次性簽名，與 $vk$ 相關，具體步驟如下：
a. 計算 $c$，即訊息 $m$ 中 0 的數量的二進位表示。
b. 形成字串 $w = m \parallel c = (a_1, a_2, \ldots, a_t)$。
c. 找出 $w$ 中 1 的坐標位置 $i_1 < i_2 < \ldots < i_u$，使得 $a_{i_j} = 1$，且 $1 \leq j \leq u$。
d. 當且僅當 $v_{ij} = h(s_j)$ 對於所有 $1 \leq j \leq u$ 時，接受 $\sigma$。

如果步驟 1 和 2 都被驗證，則 $(vk, \Sigma, \sigma)$ 是訊息 $m$ 的有效在線/離線簽名。

### Batch Signature Scheme based on RSA
> 允許一次生成或驗證多個簽名。
RSA 的批量驗證。

假設 $S_1, S_2, \ldots, S_n$ 是對雜湊值 $M_1, M_2, \ldots, M_n$ 的 RSA 簽名。
簽名者向驗證者發送配對 $(m_1, S_1), (m_2, S_2), \ldots, (m_n, S_n)$。

然後，驗證者按照以下步驟進行，使用批量驗證測試來決定 $S_i = M_i^{d} \mod N$，其中 $i = 1, \ldots, n$：
1. 計算 $H(m_i) = M_i$ 對於所有 $i = 1, 2, \ldots, n$。
2. 隨機選擇 $s_1, s_2, \ldots, s_n \in \{0,1\}^l$。
3. 計算 $x = (\prod_{i=1}^{n} S_i^{S_i})^e \mod N$ 和 $y = \prod_{i=1}^{n} M_i^{S_i} \mod N$，其中 $e$ 是簽名者的 RSA 公鑰。
4. 如果 $x = y$，則接受；否則，拒絕。

### Server-Aided Signature Scheme based on RSA
> 允許客戶從不可信的伺服器借用計算能力，而不揭露秘密。

要計算 $M^d$，首先預計算並存儲 $M^{x_0}, M^{x_1}, \ldots, M^{x_{r-1}}$，對於一些整數 $x_0, x_1, \ldots, x_{r-1}$，
然後找到 decomposition $d = \sum_{i=0}^{r-1} a_i x_i$，其中 $0 \leq a_i \leq h$ 對於 $0 \leq i \leq r - 1$。


### ID-based Signature Scheme（IBS）

#### Concept
每位參與者使用他的 ID/電子郵件 作為他的公鑰。
對應的私鑰必須由可信的中心計算，而不是由用戶自己計算。


#### Procedure
**TC 計算**：
1. 計算 $v_1 = f(I, l)$，對於小值的 $l$。
2. 選擇 $k$ 個不同的 $l$ 值，例如 $l_1, l_2, \ldots, l_k$，使得 $v_1$ 是 modulo $N$ 的二次剩餘，並計算 $v_1^{-1}$ 模 $N$ 的最小平方根 $s_1$。
3. 發行一個智能卡，該卡包含 $I$、$k$ 個 $s_1$ 值及其索引。

**用戶 I 簽署消息**：
1. 隨機選擇整數 $r_1, \ldots, r_t \in [0, N)$，並計算 $x_i = r_i^2 \mod N$。
2. 計算 $b = f(m, x_1, \ldots, x_t)$，並將 $e_{i,j}$ 定義為 $b$ 的前 $kt$ 位，其中 $1 \leq i \leq t$，$1 \leq j \leq k$。
3. 計算 $y_i = r_i \prod_{e_{i,j=1}} s_{l_j} \mod N$，對於 $1 \leq i \leq t$。

因此，$(e_{i,j}, y_i)$ 對於所有 $1 \leq i \leq t$，$1 \leq j \leq k$ 是消息 $m$ 的簽名。

**任何人都可以驗證消息 m 的簽名 $(e, y)$**：
要驗證 $(e_{i,j}, y_i)$ 是否為消息 $m$ 的有效簽名，驗證者需要執行以下操作：

**要確認簽名驗證的完成，請注意以下幾點**：

## Increase Security

### Fail-Stop Signature Scheme
> 如果有人成功偽造了一個簽名，則所謂的簽署者可以證明這是偽造的。
> 一旦檢測到偽造，簽名算法將不再使用，因此稱之為 fail-stop。

#### Procedures $ Algorithms
Fail-Stop Signature 為發件人提供了防範「具有無限計算能力的偽造者」的安全性。

兩種過程：
1. *Sign*：用於簽署訊息的算法。
2. *Verify*：用於驗證簽名的算法。

兩種演算法：
1. *Prove*：用於證明偽造的算法。
2. *Proof-test*：用於測試偽造證明的算法。

#### Properties
一個安全的 Fail-Stop Signature Scheme 必須滿足以下特性：
1. 如果簽署者簽署了一個訊息，則接收者可以驗證該簽名。
2. 一個「**polynomially bounded** 的偽造者」，無法創建成功通過驗證測試的偽造簽名。
3. 當一個「**unlimited computational power** 的偽造者」成功偽造了一個通過驗證測試的簽名時，假定的簽署者可以構建一個偽造證明，並說服第三方發生了偽造。
4. 一個 polynomially bounded 的簽署者，不能創建「其可以在後來證明為偽造」的簽名。

### Arbitrated Signature Scheme
> 會部署「對稱式金鑰」在數位簽章的方案。


#### Key Generation
仲裁者選擇一個秘密金鑰 $K_T$ ∈ $K$，其中 $K$ 是金鑰空間。
每個用戶 $A$ 選擇一個隨機的秘密金鑰 $K_A ∈ K$ 並通過**安全**和**可靠**的通道將其發送給仲裁者。

#### Signature Generation
為了替訊息 $m$ 生成簽名，$A$ 進行以下操作：

一但收到 $u$, $M$ 和 $I_A$，仲裁者進行以下操作：

#### Signature Verification
為了驗證 Alice 在消息 $m$ 上的簽名，Bob 進行以下操作：

在收到 $v$、$S$ 和 $I_B$ 後，仲裁者進行以下操作：

在收到 $w$ 和 $M \parallel I_A$ 後，Bob 進行以下操作：

### Threshold Signature Scheme
- *Dealing* 階段：dealer 將密鑰 $d$ 分發給 $n$ 位玩家。
- *Signature* 階段：$t$ 位玩家可以合作為訊息 $m$ 生成簽名。

### Proactive Signature Scheme
- 將 Threshold Scheme 中使用的「金鑰分配概念」與「金鑰分享更新概念」結合起來，共享金鑰會在頻繁的時間間隔內更新。
- 如果一個方案在「任何給定的時間間隔內」即使「最多有 $t$ 位玩家被破壞」，而仍然是安全和穩健的，則該方案稱 *$t$-proactive*。


### Forward Secure Signature Scheme
> 即使在 secret signing key 被竊取後，仍能保護「先前簽署」的訊息的有效性。

#### Idea
將總時間劃分為多個時間段，每個時間段使用不同的秘密金鑰。
公鑰保持不變；後續的秘密金鑰由金鑰更新算法更改。
即使當前的秘密金鑰被竊取，先前的秘密金鑰也無法從這個已揭露的金鑰計算得出。

#### Key Generation
為了生成總時間 T 的公鑰和初始秘密金鑰 $𝑠𝑘_1$，簽名者執行以下操作：

然後，初始時間段的秘密金鑰為 $𝑠𝑘_1 = (1, 𝑠_1, 𝑡_2, 𝑒_1, 𝑝, 𝑁)$，而公鑰 $𝑝𝑘_1$ 為 $(𝑁, 𝑣, 𝑇)$。

#### Update Algorithm
要從先前的秘密金鑰 $𝑠𝑘_j = (1, 𝑠_j, 𝑡_{j+1}, 𝑒_j, 𝑝, 𝑁)$ 生成時間 j+1 的秘密金鑰，簽署者執行以下操作：

故新密鑰為 $𝑠𝑘_{j+1} = (j+1, 𝑠_{j+1}, 𝑡_{j+2}, 𝑒_{j+1}, 𝑝, 𝑁)$。

#### Signature Generation
為了使用當前的簽名金鑰 $𝑠𝑘_j = (1, 𝑠_j, 𝑡_{j+1}, 𝑒_j, 𝑝, 𝑁)$ 簽署消息 $m$，簽署者執行以下操作：

然後 $(𝑧, 𝜎, 𝑗, 𝑒_j)$ 是消息 $m$ 的簽名。

#### Signature Verification
為了驗證 $(𝑧, 𝜎, 𝑗, 𝑒_j)$ 是消息 $m$ 的有效簽名，驗證者執行以下操作：

## Anonymous Service

### Blind Signature Scheme
> 兩名角色：Requester、Signer。

Signer 在**不知道消息內容的情況下發出盲簽名**，並且**無法將 Requester 的簽名消息與 Requester 相關聯**。

#### Signature Generation

#### Signature Verification

#### Two Drawbacks
1. 未見過的「已簽章的訊息」。
2. 不可追蹤（許多副本和重複消費）。

### Partially Blind Signature Scheme

#### Blinding
為了在消息 $m$ 上獲取「包含 **common information** $𝑎$」的簽章，請求者執行以下步驟：

#### Signing
一收到 $(a, \alpha)$，簽章者執行以下步驟：

#### Unblinding
> Requester -> Signer

一收到 $x$，請求者執行以下步驟：

> Signer -> Requester


> Requester


則 $(𝑎, 𝑐, 𝑠)$ 是消息 $m$ 的**部分盲簽名**。

#### Signature verification
可以通過檢查以下內容來驗證 $(𝑎, 𝑐, 𝑠)$ 是否是消息 $m$ 的正確簽名：

### Fair Blind Signature Scheme

一個可信的第三方擁有一些額外的信息，可以用來**撤銷嫌疑犯的匿名性**。
裁判可以將簽署者「對簽署過程的觀察」與「產生的 message-signature pair」聯繫起來。

#### Key Generation
簽署者選擇一個 RSA 公鑰 $(N,e)$ 和相應的私鑰 $d$。
請求者和簽署者同意一個 session identifier $ID$，其中簽署過程的每個實例都對應於不同的 $ID$。

#### Signature Generation

然後，$s$ 與一組對 $𝑇 = \{(𝛼_i, 𝑣_i) |𝑖 ∉ 𝑆\}$ 是在消息 $m$ 上得到的**公平盲簽名**。

#### Signature Verification

#### Fairness
假設裁判得到一個值 $𝑢_i$ 其中 $𝑖 ∈ 𝑆$。
然後，由於 $𝑢_i = 𝐸_J(𝑚 ∥ 𝛼_i)$，而 $𝐸_J$ 是裁判的加密函數，裁判可以用他的私鑰解密其中一個值，並獲得 $(𝑚 ∥ 𝛼_i)$ 對於某個 $𝑖 ∈ 𝑆$。

假設裁判得到了簽名 $(𝑠, 𝑇)$。
通過解密 $𝑇$ 中的某個 $𝑣_i$，裁判可以獲得 session identifier $ID$。
這樣，裁判就可以找到對應於給定 message-signature pair 的簽名過程實例。

### Group Signature Scheme

允許一組成員代表整個小組簽署消息。
群組簽名可以在**不揭示簽署者身份**的情況下進行驗證。
群組管理者可以 **「揭示」簽名**，以在爭議發生時揭示簽署者的身份。

#### Key Generation
群組成員的私鑰和公鑰生成方式如下：

則群組成員 $j$ 的私鑰為 $𝑠_j$，對應的公鑰為 $𝑦_j$。

#### Signature Generation
為了對消息 $𝑚 ∈ \{0,1\}^∗$ 簽名，群組成員 $j$ 執行以下操作：

故群組簽章為 $(R,S,j)$。

#### Signature Verification
為了驗證 $(𝑅, 𝑆)$ 是消息 $m$ 的有效群組簽名，驗證者執行以下操作：

#### Opening Signatures
在**發生爭議**的情況下，群組管理者可以通過查找公鑰中的編號 $j$，從列表 $(𝑧_j, 𝐼_j)$ 中，識別簽署者，並獲取群組成員的身份 $𝐼_j$。

### Ring Signature Scheme
這種簽名方法接近 Group Signature，但沒有群組管理者。
因此，**無法撤銷簽署者身份的匿名性**。


## Increase Capability

### Proxy Signature Scheme
- 允許「指定方」代表原簽署者進行簽名。
- 代理簽名的驗證方式與 Original Signature 相似。


#### Original Signature
$x \in \mathbb{Z}_p$ 是 A 的私鑰，$y = g^{x} \mod p$ 是 A 的公鑰。
要簽署消息 $m \in \{0,1\}^*$，原始簽署者選擇一個隨機數 $k \in \mathbb{Z}_p$，並計算：

然後 $(R, S)$ 是消息 $M$ 的簽名。
簽名驗證是通過檢查是否 $M \equiv g^{-S} y^R R(mod\ p)$ 來完成的。
這是有效的，因為：

#### Key Delegation

代理簽名密鑰的驗證是可運作的，因為：

#### Proxy Signature Generation

#### Signature Verification
要驗證這個簽名，驗證者計算 $𝑀 = 𝐻(𝑚)$ 並檢查是否滿足 $𝑀 ≡ 𝑔^{-S}y^{'R}R\ (mod\ 𝑝)$。
如果這個方程成立，則接受該簽名，否則拒絕。

代理簽名的驗證是可運作的，因為：

### Undeniable Signature Scheme
- 為簽名者提供額外的隱私，因為在**沒有簽名者合作**的情況下，無法驗證簽名。
- 只有「簽名者希望進行通訊」的各方才能驗證簽名。
- 如果簽名者「聲稱某個簽名是偽造的」，則可使用 Disavowal protocol，他有手段證明其為偽造。
- 如果簽名者「拒絕證明簽名是偽造的」，這將成為簽名有效的證據。


#### Key Generation
每位使用者 A 執行以下步驟：

此時 A 的公鑰是 $(p,\alpha,y)$；私鑰是 $a$。

#### Signature Generation
A 計算 $𝑆 = 𝑚^a\ 𝑚𝑜𝑑\ 𝑝$。
故 A 對 $m \in G$ 的簽章是 $S$。

#### Signature Verification

#### Disavowal Protocol
為了確保簽名者**正確執行驗證協議**，簽名者和驗證者之間進行以下協議：

### Convertible Undeniable Signature Scheme

具有附加屬性，簽名者可以**釋放一部分秘密訊息**，使其所有「Undeniable signatures」轉變為「Ordinary digital signatures」。

#### Key Generation

#### Signature Generation

#### Signature Verification
驗證者接受簽名 $(\tilde R, S)$－
是否 $\log_{H_G(\alpha^Sy_1^{H_l(m,\tilde R)})}\tilde R \equiv log_{\alpha}\ y_2$，若等式不成立則拒絕。

要將此簽名方案轉換為普通數位簽名方案，簽署者公佈他的秘密金鑰 $x$。
然後，任何人都可以通過檢查以下條件，來驗證他的簽名：


### Designated Confirmer Signature Scheme
> 一種 undeniable signature，該簽名可以**由簽署者指定的第三方證明其有效性**。

設 $p$ 是一個大質數，使得在 $\mathbb{Z}_{p}^{*}$ 中的離散對數問題是 generator。
設 $(N,e)$ 是簽署者的 RSA 公鑰，其中 $d$ 是對應的私鑰。
確認者的私鑰是 $\mathcal{z} \in \mathbb{Z}_{p}^{*}$，對應的公鑰是 $h = g^{\mathcal{z}} \mod p$。

#### Signing Protocol

#### Confirmation Protocol

#### Conversion Protocol