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

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

基礎密碼學演算法：RSA

假設 Bob 要將訊息

$m$ 傳給 Alice 。

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

產生金鑰

1. Alice 隨機生成兩個大質數
   $p,q$ ，並且令
   $N=pq$ 。
   • $N$ 建議至少 2048 個位元。
2. Alice 選擇一個大整數
   $e$ 且
   $gcd(e,\phi (N))=1$ 。
   • $\phi (x)$ 為歐拉函數，即小於
     $x$ 且與
     $x$ 互質之正整數的數目。
   • 通常選
     $e=65537$ 。
     • 若
       $gcd(e,\phi (N))\ne 1$ ，重選一個適合的
       $N$ 。
3. 令
   $d=e^{-1}(\mathrm{mod}\phi (N))$ 。
   • 因為
     $\phi (n)=(p-1)(q-1)$ 不是質數，這樣的
     $d$ 可能不只一個。隨意選擇一個即可。

Alice 得到公鑰

$P=(N,e)$ 和私鑰

$S=(N,d)$ 。

訊息傳遞

1. Alice 公開她的公鑰
   $P=(N,e)$。
2. 令 Bob 想傳送的明文訊息為
   $m$，計算
   $m^{\prime }=m^e(\mathrm{mod}N)$ 。顯然
   $gcd(m,N)=1$ 的機率極高。
3. Bob 傳送
   $m^{\prime }$ 給 Alice 。
4. Alice 以私鑰
   $S=(N,d)$ 得到
   $m=(m^{\prime }{)}^d(\mathrm{mod}N)$。因為
   $$(m^{\prime }{)}^d=m^{ed}=m^{1+k\phi (N)}=m\cdot {\left(m^{\phi (N)}\right)}^k=m\cdot (1{)}^k=m(\mathrm{mod}N)$$
   • 歐拉定理：
     $\mathrm{\forall }a,b\in \mathbb{N},gcd(a,b)=1⟹a^{\phi (b)}=1(\mathrm{mod}b)$

投票系統之設計原則

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

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

我的演算法將致力於：

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

我的演算法將不試圖：

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

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

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

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

投票步驟

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

開票步驟

郁雯從投票箱拿出一張選票，令其為

$b$ 。
假設這張選票來自水豚，故

$b=m^{‴}=m^d(\mathrm{mod}N)$ 。

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

選舉的可驗證性

投票特性與待討論事項

平等原則

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

匿名原則

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

選舉之可驗證性

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

待討論

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

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

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

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

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

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

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

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

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

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