瑞士郵政電子投票系統應該如何運作，它是如何出錯的？
我讀到瑞士郵報開發了一個電子投票解決方案，可以獲取原始碼進行審查，並且發現了漏洞。
顯然，我們不是在談論電子投票的固有和眾所周知的問題：它不能阻止購買選票，而選民設備的滲透可以讓投票扭轉局面。我們也不是在談論 IT 基礎設施的（據說是可笑的）程式碼質量，或者它對拒絕服務攻擊的脆弱性。
不，它是由三個獨立的團隊發現的某種密碼缺陷：
- Sarah Jamie Lewis、Olivier Pereira 和 Vanessa Teague：Ceci n’est pas une preuve，在 Bayer-Groth 證明中使用陷門承諾及其對 Scytl-SwissPost 網際網路投票系統可驗證性的影響（見介紹）
- Rolf Haenni：Swiss Post Public Intrusion Test：無法檢測到的針對投票完整性和保密性的攻擊（參考頁面）。
- 托馬斯·埃德蒙·海恩斯 ( NTNU )。
提議的系統應該如何工作，它或它的實施有什麼問題？
官員們可以放心：部署的電子投票系統不會有這個缺陷。
在瑞士郵政的電子投票協議中，在選民送出選票後，它們會被單獨打亂，然後一起洗牌，這樣在統計之前就無法追溯到選民來找出誰投票給了誰——通常稱為選票保密、隱私或匿名.
但由於選票是電子系統中的比特，而不是物理人工製品，因此很容易在實現洗牌器的電腦中的魔法振動矽晶體中製造洗牌的選票。因此，洗牌員還必須列印一張收據，世界上任何人都可以用它來驗證這只是洗牌，而不是任何其他類型的更改——這是選舉普遍可驗證性的一部分——同時仍然保密誰投票給誰。
與任何具有選票保密的電子投票協議一樣，瑞士郵政協議中的普遍可驗證性方法涉及大量複雜的數學。事實證明，數學的設計方式使選票洗牌器能夠輕鬆偽造一張收據，以改變選舉結果的欺詐性“洗牌”。
它是如何工作的？
讓 $ m_1, m_2, \dots, m_n $ 在選舉中代表填寫好的選票。我們希望對選票保密，但要計算投票數，並讓公眾驗証投票數。
投票站工作人員查看誰送出了每張選票 $ m_i $ ，所以我們首先將選票加密為 $ c_i = E_k(m_i, \rho_i) $ 向投票站工作人員隱瞞，投票站工作人員將其放入選票堆中， $ E_k(m, \rho) $ 是具有隨機化的隨機公鑰加密方案 $ \rho $ . 隨機化意味著投票工作人員不能只檢查是否 $ c_i = E_k(b) $ 對於每一個可能的選票 $ b $ 恢復什麼 $ m_i $ 是。
知道秘密密鑰的投票計數器，然後取出一堆加密選票，解密它們，併計算結果。
- 由於投票工作人員可以傳遞誰按哪個順序投票，我們需要一個選票洗牌器的幫助來將選票洗牌 $ c_{\pi(1)}, c_{\pi(2)}, \dots, c_{\pi(n)} $ 對於秘密排列 $ \pi $ .*
- 由於計票器可以眼球 $ c_{\pi(i)} $ 辨別是否相同 $ c_j $ 從而恢復什麼 $ \pi $ 也就是說，我們還要求洗牌器在不更改其隱藏的選票的情況下對每張選票進行打亂。
如果 $ E_k $ 在消息和隨機化中是同態的，意思是$$ E_k(m_1 m_2, \rho_1 + \rho_2) = E_k(m_1, \rho_1) \cdot E_k(m_2, \rho_2), $$然後我們可以通過$$ c’i = c{\pi(i)} \cdot E_k(1, \rho’i) = E_k(m{\pi(i)}, \rho_{\pi(i)} + \rho’_i) $$用於秘密隨機化 $ \rho’_i $ . * 然後我們通過 $ c’_1, c’_2, \dots, c’_n $ 到投票櫃檯。
市民只有自己的收據 $ c_i $ ，沒有私鑰，它們彼此之間以及與 $ c’_i $ . 確信**計票器或洗牌器不會通過替換來欺詐性地改變選舉結果 $ m_i $ 被一些惡意的 $ \hat m_i $ ，該系統必須對公眾成員是可驗證的。†
同態隨機公鑰加密方案的典型範例是 Elgamal 加密 $ E_k(m, \rho) := (g^\rho, k^\rho \cdot m) $ 在哪裡 $ g, k, m \in G $ 是一個組的元素 $ G $ 其中離散日誌是困難的，而密鑰 $ k $ 是指數 $ x $ 這樣 $ k = g^x $ . 這裡是密文的乘法 $ (a, b) \cdot (c, d) $ 是元素方面的， $ (a \cdot c, b \cdot d) $ .
多年來已經有許多效率不同的系統來證明洗牌器發送到投票櫃檯進行統計的實際上是一組 $ c_{\pi(i)} \cdot E_k(1, \rho’_i) $ . ‡ 其中之一是Bayer-Groth（全文）。在數十年的工作基礎上進行了大量加密數字化，以製作有效的非互動式零知識證明——任何公眾都可以離線使用的收據來驗證 $ c’i $ 實際上是 $ c{\pi(i)} \cdot E_k(1, \rho’_i) $ , 不學什麼 $ \pi $ 或者 $ \rho’_i $ 是。
有問題的關鍵部分是使用Pedersen 承諾來承諾指數 $ a_1, a_2, \dots, a_n $ 隨機化 $ r $ 通過分享承諾 $$ \operatorname{commit}_r(a_1, a_2, \dots, a_n) := g_1^{a_1} g_2^{a_2} \cdots g_n^{a_n} h^r, $$其中組元素 $ g_1, g_2, \dots, g_n, h \in G $ 是獨立均勻隨機選擇的。
承諾本身沒有提供關於 $ (a_1, a_2, \dots, a_n) $ 沒有 $ r $ 因為所有承諾都是等機率的，如果 $ r $ 是一致的——也就是說，Pedersen 承諾在理論上是隱藏的。但是承諾和隨機化 $ r $ 使任何人都能驗證任何假定的方程 $ (a’_1, a’_2, \dots, a’_n) $ 獲得信心，他們是 $ (a_1, a_2, \dots, a_n) $ 用於首先創建承諾：如果你能找到一個不同的序列 $ (a’_1, a’_2, \dots, a’_n) \ne (a_1, a_2, \dots, a_n) $ 和隨機化 $ r’ $ 為此$$ \operatorname{commit}r(a_1, a_2, \dots, a_n) = \operatorname{commit}{r’}(a’_1, a’_2, \dots, a’_n), $$ 那麼你可以計算離散日誌 $ h $ 和 $ g_i $ 相對於彼此——一個簡潔的總結是，在離散對數假設下，Pedersen 承諾在計算上具有約束力。（證明：如果 $ g_1^{a_1} h^r = g_1^{a’1} h^{r’} $ ， 然後 $ \log{g_1} h = \frac{a’_1 - a_1}{r - r’} $ .)
Bayer-Groth 洗牌器使用 Pedersen 承諾來承諾一個 $ \pi $ 和隨機化值 $ \rho’_i $ 在收據中，公眾可以用來驗證送出給投票櫃檯的一組選票。 如果選票洗牌器可以撒謊並聲稱使用排列 $ \pi $ ，雖然他們實際上使用了重複某些投票並丟棄其他投票的功能，但他們可以欺詐性地改變選舉結果。Lewis-Pereira-Teague 的論文 詳細介紹了它的工作原理。
- 看待這種對 Pedersen 承諾的依賴的一種方法是離散對數問題似乎很難，所以我們只需要選擇承諾基數 $ g_1, \dots, g_n, h $ 獨立均勻隨機。
隨機均勻地選擇群元素的明顯方法是選擇指數 $ e_1, \dots, e_n, f $ 獨立均勻地隨機設置 $ g_1 := g^{e_1}, \dots, g_n := g^{e_n}, h := g^f $ . 這就是 Scytl/瑞士郵政系統所做的。
- 另一種看待這個的方式是神聖的狗屎，指數 $ e_1, \dots, e_n, f $ 是一個秘密的後門，知道後門將使選票洗牌者能夠進行本質上任意的選票欺詐——就像 Dual_EC_DRBG 基點一樣。
選舉機構可以通過使用另一種方法（如FIPS 186-4 附錄 A.2.3 ）選擇承諾基礎來緩解這種情況，這可能使學習後門指數變得困難，並且可以驗證；據稱這是 Scytl 選擇解決問題的方法，儘管我不知道他們是否發布了進行驗證所需的雜湊原像。
這聽起來像是一個微不足道的錯誤：哎呀，我們忘記將秘密歸零了。但它說明了一個更深層次的問題。
承諾基礎 $ g_1, \dots, g_n, h $ 用作標準技術（免付費牆）中的通用參考字元串，用於將互動式零知識證明系統轉換為非互動式零知識證明收據，如投票洗牌器應該列印出來的。
在互動式證明系統中，驗證者可能會選擇一個不可預測的挑戰——比如阿里巴巴和 40 大盜的故事中從哪條隧道出來——證明者必須正確回答。如果我們想製作一個非互動式的證明收據，我們可以在網站上發布供公眾下載和驗證怎麼辦？
- 在某些協議中，例如Schnorr使用Fiat-Shamir 啟發式推導出的簽名方案，挑戰可以由隨機預言代替：證明者可以在迄今為止的成績單上評估的隨機函式，以模仿驗證者可能無法預測的挑戰已送出，但證明者無法控制。為了實例化這樣的協議，我們選擇了一個像 SHAKE128 這樣的雜湊函式，我們希望它沒有有用的屬性，證明者可以利用它來偽造欺詐證明。
附錄：這篇文章已經太長了，但在報告此處詳述的缺陷兩週後，同一位研究人員報告了另一個導致欺詐的缺陷，即濫用 Fiat-Shamir 啟發式——設計者忽略了提供整個抄本將值送出到散列函式（“隨機預言機”）中，這對於 Fiat-Shamir 啟發式的安全性至關重要。儘管NSWEC 公開聲稱不受影響（存檔） ，但該漏洞也出現在新南威爾士州選舉委員會基於 Scytl 軟體的 iVote 系統中。
- 類似地，在像 Bayer-Groth 這樣的一些協議中，我們可以使用一個通用的參考字元串：一個預先確定的隨機選擇的比特串，並且預先為驗證者和證明者所知。為了實例化這樣的協議，我們需要一個系統來提前選擇一個隨機字元串，證明者可以利用其屬性的機率可以忽略不計，就像我們在 FIPS 186-4 附錄 A.2.3 中得到的那樣。 如果證明者可以影響公共參考字元串，則證明沒有任何意義。
這是密碼系統**安全合約的一部分。**要從 AES-GCM 中獲得任何安全性，您的義務是隨機統一選擇密鑰並將其保密，並且永遠不要以相同的 nonce 重複使用它。為了從 Bayer-Groth 投票洗牌器中獲得任何安全性，驗證者和證明者必須事先就證明者無法控制的公共參考字元串達成一致。 在 Scytl 系統中，證明者選擇了公共參考字元串。 這不僅違反了安全契約，而且表明他們對他們使用的非互動式零知識證明系統的基本前提的理解嚴重失敗。
公開證據尚不清楚作者是否知道這將成為後門，Lewis-Pereira-Teague 的論文警告說，這可能是無能而非惡意的產物——該缺陷的技術性質自 2017 年以來在內部就為人所知（存檔）但不清楚後果是否被理解。NIST 採用 Dual_EC_DRBG 可能是 NIST 的無能——NIST 很早就意識到基點存在問題，並被 NSA 告知不要討論它。
首要任務不是爭論軟體供應商 Scytl 是惡意還是無能，而是要被選舉當局認真對待，要求對設計進行真正的審查，而不是在部署之前受到 NDA 阻礙的虛假漏洞賞金，以及回顧我們如何到達這裡的過程，以確保像這樣的帶有後門的設計永遠不會接近在真正的選舉中部署，因為它們會導致極其便宜的任意大規模無法驗證的投票欺詐。
（人們可以爭論更大的問題是否來自電子投票中無法察覺的集中欺詐；郵寄投票中的分佈式欺詐；或通過選區劃分、重罪剝奪選舉權和關閉投票站來壓制選民。人們可以爭論其他 IT 問題，關於重要性紙質記錄和強制性風險限制審計等*。*應該有這樣的論點，但這個問題不是他們的論壇——考慮志願擔任選舉工作人員或與你的議會交談！這個問題專門針對 Scytl 和瑞士郵政對密碼學的誤用（無論是疏忽還是惡意）的技術性質。）
*我們假設有一個無所不知的大規模監控制度監控選票洗牌員的每一個動作，以確保他們不會與其他任何人勾結以洩露無記名選票。無所不知的大規模監視制度也是誠實的，並且永遠不會夢想與任何人勾結——不是有意的。
†我們假設公眾完全由擁有密碼學博士學位的人組成，例如瑞士。
‡計票器還必須能夠證明它返回的計數是提供給它的加密選票的明文總和，我們不會在這裡討論——這裡討論的具體後門在投票洗牌器中.