# [Blind Signature] Blind Signatures for Untraceable Payments

[論文連結 Blind Signatures for Untraceable Payments, David Chaum 1982](https://sceweb.sce.uhcl.edu/yang/teaching/csci5234WebSecurityFall2011/Chaum-blind-signatures.PDF)

為了因應自動付款與未來電子支付系統而提出的簽章機制，希望付款系統能夠考量下列兩個安全問題:
1. 第三方可以透過商品明細、消費地點、消費金額，得到個人的相關資訊，例如住址、生活方式等等
2. 鈔票、硬幣等匿名的付款方式(錢幣上面不會寫名字)，會因為無法提出交易證明，可能會有黑金賄賂、逃稅、黑市等相關問題

因此本論文在此提出一個新的簽章機制能夠讓自動支付系統擁有下列三種特性:
1. 第三方(例如銀行)無法確認付款人、交易時間、金額等資訊
2. 特殊情況下(例如調查賄賂案件)，個人可以提供交易證明或是確認付款人身分
3. 如果支付的媒介被偷走了可以通報並且使其無法繼續使用(應該是像信用卡掛失的服務)

## Basic Idea
盲簽章在現實世界中的一個應用，例如在信封內放入碳式複寫紙(carbon paper)，在信封上面簽名，透過複寫紙簽到信封內的紙

假設今天受託人(trustee)要舉辦不記名的投票選舉，但是選舉人無法到現場親自投下他們的票，每一位選舉人都希望他們選票的內容能夠保密，並且選舉人能夠驗證他們投的票是否被計算在內

1. **選舉人**將寫有他們投票內容的選票放入碳襯信封(carbon lined envelope)，將碳襯信封放到要寄給受託人的外部信封，上面寫回寄地址後寄給受託人
2. **受託人**打開外部信封，取出裡面的碳襯信封在上面簽名，把簽名後的碳襯信封裝到新的外部信封後寄回去給選舉人
3. **選舉人**打開外部信封取出碳襯信封，把碳襯信封裡的選票拿出來，此時的選票上會有受託人的簽名，等到選舉當天選舉人把有簽名的選票匿名寄給受託人
4. 任何人都可以檢驗選票是否合法，並且計數

受託人在簽名時完全不知道選票的內容，在計票的時候也不會知道這張選票是誰投的，上面只有投票的內容和受託人的簽章(假設受託人的簽章長得一模一樣)，如果選舉人有在選票上做只有他們自己可以認得的記號，他們也可以確認自己的選票是否被計算在內

## Funcitons
**1. Signing function**
$s'$ 只有 signer 知道(類似 secret key)
$s$ 公開的 inverse of $s'$(類似 public key)，$s(s'(x))=x$
**2. Commuting function**
$c$ 和其 inverse $c'$ 只有 provider 知道，$c'(s'(c(x)))=s'(x)$
$c(x)$ 可以看做把選票放進碳襯信封裡面，$s'(c(x))$ 是在碳襯信封上面簽名，$c'(s'(c(x)))=s'(x)$ 則是把碳襯信封裡的選票拿出來得到有簽名的選票 $s'(x)$
**3. redundancy checking predicate $r$**
A redundancy checking predicate r, that checks for sufficient redundancy to make search for valid signatures impractical.
> [name=育靜]
> 不是很確定這東西的功能，看起來像是對訊息加上亂數
> [name=丁哥]
> 像是 hash 而且功能就是防止 existential forgery
>
> **存在性不可偽造(Exsistent Unforgeability)**
> 以 RSA 簽章為例，如果直接用私鑰 $d$ 對訊息 $m$ 簽章，得到 $\sigma = m^d$，用公鑰 $e$ 可通過驗證 $\sigma^e = m^{ed} = m$，$\sigma$ 也可以看做是一種亂數，Adversary 可以利用隨機挑選的亂數 $r$ 乘上 $e$ 次方得到 $r^e = m'$，$r$ 即是 $m'$ 對應的簽章，且 Adversary 不知道私鑰 $d$
>
> 如果改成對訊息摘要 $H(m)$ 簽章，得到 $\sigma = H(m)^d$，且 $\sigma^e = H(m)$，訊息 $m$ 是公開的，驗證時除了使用公鑰得到 $H(m)$ 之外，還需要訊息 $m$ 來產生 $H(m)$ 比對兩者是否相同，所以即使 Adversary 挑選亂數 $r$ 來計算 $r^e$ 也只能算出某個 Hash 後的值，不知道對應的訊息

## Protocol
整個協定中存在兩個主要角色 Signer 和 Provider
1. Provider 隨機挑選一個亂數 $x$，計算 $r(x)$、$c(x)$，將 $c(x)$ 傳送給 Signer
2. Signer 對 $c(x)$ 簽章，得到 $s'(c(x))$ 回傳給 Provider
3. Provider 計算 $c'(s'(c(x)))=s'(x)$
4. 任何人可以對公開的 $s'(x)$ 驗證 $r(s(s'(x)))$，如果整個簽章程序都是正確且合法的，理論上 $r(s(s'(x)))=r(x)$

> [name=育靜]
> 這裡看 $r()$ 的用法很像是 hash 的功能

## Properties
**1. Digital Signature**
任何人可以用 Signer 的公鑰驗證簽章的合法性
**2. Blind Signature (Blindness)**
不希望 Signer 知道簽的訊息內容，因此要求 Signer 無法分辨 $s'(x_i)$ 和 $s'(c(x_i))$ ($s'(x_i)$ 和 $s'(c(x_i))$ 之間沒有關聯性)
**3. Conservation of Signatures (one-more unforgeability)**
Provider 即使看到 $s'(c(x_1)), ..., s'(c(x_n))$ 這麼多個簽章，其中 $c, c', x_i$ 還是 Provider 挑的，但是他還是無法自己產生簽章 $s'(y)$ 使得 $r(y), y \neq x_i$

## Untraceable Payments System
回應前面論文目標是要將盲簽章應用在付款系統上，把論文中的流程用圖表現如下，總共包含三個角色，付款人(payer)、收款人(payee)、銀行(bank)，其中銀行的公鑰為$s$，私鑰為$s'$:
1. 付款人隨機挑選亂數 $x$，計算 $r(x)$ 和 $c(x)$
2. 付款人傳送 $c(x)$ 給銀行
3. 銀行對 $c(x)$ 簽章 $s'(c(x))$，並對付款人帳戶扣款
4. 銀行把簽章 $s'(c(x))$ 回傳給付款人
5. 付款人把複印好的簽章拿出來 $c'(s'(c(x)))=s'(x)$
6. 付款人檢查簽章合法性 $s(s'(x))=x$
7. 付款人把有銀行簽章的訊息 $s'(x)$ 給收款人
8. 收款人檢查簽章 $s'(x)$，$r(s(s'(x)))$
9. 收款人把簽章 $s'(x)$ 給銀行
10. 銀行檢查簽章，$r(s(s'(x)))$
11. 銀行確認簽章合法後，紀錄簽章訊息 $s'(x)$ 到列表上
12. 銀行撥款到收款人帳戶
13. 銀行通知收款人已受理交易
> [name=育靜]
> 論文裡面稱 $c(x)$ 和 $s'(x)$ 都是 "note"，步驟 1~4 的 note 指的是 $c(x)$，當 payer 把碳襯信封拿掉得到 $s'(x)$ 之後 note 就變成 $s'(x)$ 了