---
tags: 匿名投票
---

# 匿名投票演算法設計計畫書

這套匿名系統計畫以 RSA 演算法為基礎實現。也可能改用橢圓加密演算法。

## 基礎密碼學演算法：RSA

假設 Bob 要將訊息 $m$ 傳給 Alice 。

1. Bob 獲得 Alice 的公鑰 $P=(N,e)$ 。
2. Bob 將明文訊息 $m$ 透過公鑰 $P$ 加密得到密文 $m'$ 。
3. Bob 將密文 $m'$ 傳給 Alice 。
4. Alice 以私鑰 $S=(N,d)$ 對密文 $m'$ 解密得到明文 $m$ 。

### 產生金鑰

1. Alice 隨機生成兩個大質數 $p,q$ ，並且令 $N=pq$ 。
- $N$ 建議至少 2048 個位元。
2. Alice 選擇一個大整數 $e$ 且 $\gcd(e,\varphi(N))=1$ 。
- $\varphi(x)$ 為[歐拉函數](https://zh.wikipedia.org/wiki/%E6%AC%A7%E6%8B%89%E5%AE%9A%E7%90%86_(%E6%95%B0%E8%AE%BA))，即小於 $x$ 且與 $x$ 互質之正整數的數目。
- 通常選 $e=65537$ 。
- 若 $\gcd(e, \varphi(N)) \neq 1$ ，重選一個適合的 $N$ 。
3. 令 $d=e^{-1} \pmod {\varphi(N)}$ 。
- 因為 $\varphi(n)=(p-1)(q-1)$ 不是質數，這樣的 $d$ 可能不只一個。隨意選擇一個即可。

Alice 得到公鑰 $P=(N,e)$ 和私鑰 $S=(N,d)$ 。

### 訊息傳遞

1. Alice 公開她的公鑰 $P=(N,e)$。
2. 令 Bob 想傳送的明文訊息為 $m$，計算 $m'=m^e \pmod N$ 。顯然 $\gcd(m,N)=1$ 的機率極高。
4. Bob 傳送 $m'$ 給 Alice 。
5. Alice 以私鑰 $S=(N,d)$ 得到 $m=(m')^{d} \pmod N$。因為 $$(m')^d = m^{ed} = m^{1+k\varphi(N)} = m \cdot \left(m^{\varphi(N)}\right)^k = m \cdot (1)^k = m \pmod N$$
- [歐拉定理](https://zh.wikipedia.org/wiki/%E6%AC%A7%E6%8B%89%E5%AE%9A%E7%90%86_(%E6%95%B0%E8%AE%BA))： $\forall a,b \in \mathbb N, \quad \gcd(a,b)=1 \implies a^{\varphi(b)}=1 \pmod b$

## 投票系統之設計原則

目前尚沒有「完美」的匿名投票演算法。一場具有公信力的網路匿名投票，一定程度上依賴以下幾點：

- 是否有第三方的中立機構共同主持選舉。
- 機關之選委會是否有公信力。
- 選民願意承受何種程度的隱私曝光。

我的演算法將致力於：

- 盡最大的可能保護選民的投票意向。
- 盡最大的可能使主辦方能自證選舉的匿名性及公正性。

我的演算法將不試圖：

- 解決連現實投票也無法排除的技術困難或倫理問題。
- 設計一套適用於邪惡的選委會的選舉演算法。
- 完美保持所有選民的匿名性、選舉的可驗證性、以及選委會的可自證中立性。這是不可能的。

## 以 RSA 為基礎的盲簽投票系統

假設郁雯是投票主管機關、水豚是投票者，並且水豚想要投給財哥。令

- 郁雯的公鑰為 $P=(N, e)$ ，這把鑰匙是早已公開的。
- 郁雯的私鑰為 $S=(N, d)$ ，這把鑰匙只有郁雯知道。
- 註：對於每一個選區，郁雯都要準備一對鑰匙。
- 水豚準備一個大整數盲化密碼 $k<N$ ，並且 $\gcd(k,N)=1$ ，這個密碼只有水豚知道。

### 投票步驟

1. 水豚在空白選票上寫下財哥的名字，加上些許雜訊（不影響選票辨認之無意義文字等）。令此張選票為 $m$ 。
2. 水豚用郁雯的公鑰 $P$ 和自己的密碼 $k$ 對選票 $m$ 加密，得到加密的選票 $m'$ $$m'=mk^{e} \pmod{N}$$
3. 水豚將加密的選票 $m'$ 交給郁雯。
- 如果水豚和郁雯之間有可靠或雙方均能接受的的信息傳輸管道（例如電子信箱），水豚可以不必給出雜湊。此時水豚不必準備一對鑰匙。
4. 郁雯檢查水豚是否已經投過票。如果有，不簽名，演算法立刻結束。
- 濫發簽名將使演算法出現漏洞，導致做票發生。務必嚴格遵守一人僅簽一次。
5. 郁雯驗證這是來自水豚的請求。
- 驗證方法可由雙方事前約定，例如電子郵件、臉書等。
- 若沒有可靠的驗證方法，則驗證雜湊。
6. 郁雯用自己的私鑰 $S$ 對加密的選票 $m'$ 進行簽名，得到認證的加密選票 $m''$ 。
- 因為郁雯只能看到 $m'$ 和 $m''$ ，看不到 $m$ ，因此郁雯沒辦法知道水豚投給財哥。 $$m''=(m')^{d}=(mk^{e})^{d}=m^{d}k^{ed}=m^{d}k \pmod{N}$$
7. 郁雯將認證的選票 $m''$ 還給水豚。
8. 水豚對認證的選票進行解密，得到 $m'''=(m'')k^{-1}=m^{d} \pmod{N}$ 。
- 水豚以先前準備的密碼 $k$ 和郁雯的公鑰 $P$ 來檢查郁雯的簽名是否正確，因為 $$(m''')^{e}=(m^{d})^{e}=m \pmod{N}$$
- 如果郁雯給出假簽名，或簽名遭到竄改，水豚可以立即發現。
9. 水豚將選票 $m'''=m^{d} \pmod{N}$ 放入投票箱。
- 此步驟不可假手他人，也不能由郁雯經手。
10. 水豚投票結束。

### 開票步驟

郁雯從投票箱拿出一張選票，令其為 $b$ 。
假設這張選票來自水豚，故 $b=m'''=m^{d} \pmod{N}$ 。

1. 因為此張選票在選票箱裡唯一，水豚可以知道這是他的選票。
- 選票裡除了財哥的名字之外，還有不影響選票辨識的雜訊。
2. 郁雯用公鑰 $P$ 對這張選票進行解密，得到解密的選票 $b'$ 。$$b'=b^e=m^{de}=m \pmod{N}$$
3. 此張選票 $b'$ 可辨識，因此財哥獲得一票。
- 若 $b'$ 可辨識，則這張票可以被證明為郁雯簽過的，因此是合法票。
- 若 $b'$ 不可辨識：
- 如果郁雯事前新增一個被選人叫做「廢票」，就能分辨這是來自投票者的廢票，還是來路不明、未經郁雯認證的假選票。
- 否則無法區分廢票與假選票。

## 選舉的可驗證性

投票特性與待討論事項

#### 平等原則

- 平等性：郁雯只會給每個人簽名一次，因此一人一票。
- 若選票箱裡出現一模一樣的選票，表示有人一票多投。
- 可事先規範這種情況應計為一票，或全部視為廢票。
#### 匿名原則

- 匿名性：郁雯看不到任何人的選票。
- 投票意向可自證：水豚可以透過展示密碼 $k$ 來嚴格證明自己真的投給財哥。
- 現實中，一個投票者很難以合法的行動證明自己投給哪位被選人。可能會透過蓋印章在特定位置等等方法來證明自己的投票意向 (2014 民進黨台南市議會) ，但證明力道弱。
- 這問題是否敏感？

#### 選舉之可驗證性

- 外部人士無法做票。
- 但外部人士的有心攻擊可以導致無意義的大量廢票。
- 因此投票管道（即投票的網站）必須保密，只有郁雯和水豚知道。
- 水豚無法做票。
- 一票多投可以視為廢票。
- 水豚使用 [Chosen-Message-Attack](https://crypto.stackexchange.com/questions/35644/chosen-message-attack-rsa-signature) 來做票沒有實質意義（參見 [Danger of RSA blind sign](https://en.wikipedia.org/wiki/Blind_signature#Dangers_of_RSA_blind_signing)）。因為作出一張有效票的代價是犧牲另一張有效票為廢票。
- 前提是郁雯不濫發簽名。
- 水豚的票被正確開出，但他謊稱沒被開出，或有開出但被竄改。
- 可以要求水豚公開他的密碼 $k$，以驗證水豚的聲明是否為真。
- 若水豚公開 $k$ ，他的投票意向會曝光。
- 若水豚以隱私為由，不願意公開 $k$ ，事情很難處理。
- 待討論。
- 郁雯無法做票。
- 郁雯做票會導致幽靈票出現，因此郁雯無法做票。
- 要檢查是否有幽靈票，恐怕需要公開有領票者的名單，才能知道投票人數。這會一定程度上降低匿名性。
- 郁雯如果給假簽名，會在交還選票的時候被水豚發現。
- 選舉結果可以被驗證。
- 如果所有人都願意證實自己的選票被正確開出，這場選舉就可以被證明為公正。
- 導致有領票者的名單曝光。
- 可以考慮要求所有投票者回報自己的選票狀況。
- 雖然這個演算法可以有效防止他人捏造選舉不公的假指控，但要自證選舉公證，仍有一定困難度。
- 因為投票人數等於開出的有效票數（含廢票），因此可以證明沒有幽靈選票。

## 待討論

目前所有問世的匿名投票演算法，均不可能同時滿足以下所有條件。因此在選舉安全性、選票匿名性、選舉可驗證性中，有必要做出相當取捨與權衡。

- 該演算法可確保且證明主辦方並未做票。
- 該演算法可確保且證明投票者最多只領一張票。
- 該演算法確保所有投票者的匿名性。
- 任何人都不知道你是否有去領票。
- 任何人都不知道你是否投廢票。
- 任何人都不知道你投給了誰。
- 該演算法確保選舉結果被輕易驗證。
- 若有人質疑為選舉結果不可靠，可證明此質疑是否有理，同時不影響任意投票人的匿名性。

以下問題的答案將決定精確的演算法的設計方向：

- 是否存在公正的第三方中立機構，可以共同主辦這次的投票？
- 第三方機構可以持有關鍵的密鑰，使演算法更易於設計，並且讓投票過程更具彈性。
- 工會會員是否均能夠信任工會之選舉委員會（以下簡稱選委會）？
- 選委會絕對不能知道任何人的投票意向。
- 工會會員是否擔心選委會製造幽靈選票？
- 工會會員是否擔心選委會給予某人多張選票？
- 工會會員是否擔心選委會吃票？
- 郁雯是否信任工會會員？
- 郁雯是否擔心工會會員做票（在匿名投票的世界裡，任何人都能做票，不是只有選委會）？
- 郁雯是否能夠接受工會會員作出不影響選舉結果的廢票？
- 郁雯是否擔心工會會員擾亂投票網站？
- 投票者的匿名程度要做到多少？
- 投票者的投票意向是絕對不能公開的。
- 是否可以公開某人是否投出有效票或廢票？
- 是否可以公開某人是否有領票？
- 是否允許投票者能夠自證投票意向？
- 對於投票者的異議，應採取什麼樣的作法，以證明選舉之公正性？
- 如果異議為真，演算法是否需能夠證明選委會的錯誤？
- 如果異議為假，演算法是否需能夠證明此異議為假？
- 是否能夠犧牲所有投票者的匿名性以證明？
- 是否能夠只犧牲該投票者的匿名性以證明？
- 選票允許以什麼樣子形式存在？
- 隨機亂數或識別碼。
- 可確保計票不會出現爭議。
- 圖像，如在被選人框框中蓋章、書寫被選人姓名等。
- 可能出現不知道是要頭給誰的模糊票。
- 筆跡或可辨識身份之符號等等是否存在匿名性問題？

上述討論的結果，將決定我的演算法是否能夠：

- 使選委會自證自己沒有放幽靈票。
- 使選委會自證自己沒有多給選票給某投票者。
- 使投票者無法自證自己的投票意向。
- 使領票者的清單保持匿名。
- 選委會一定要知道領票者的清單，才能保證一人一票。
- 使投出有效票者的清單保持匿名，且
- 僅選委會知情。
- 選委會亦不知情。

無論上述討論的結果為何，我設計的演算法，一定可以：

- 讓選委會自證無法得知任何人的投票意向。

無論上述討論的結果為何，我設計的演算法，一定無法：

- 讓選委會自證沒有側錄投票者的 IP 位址、投票時間、瀏覽器（例如某人使用相當罕見的瀏覽器，藉此可以推測出來自該瀏覽器的選票是他投的）等資訊。
- 僅能透過選委會的公信力，或透過第三方的中立機構解決。