[IT-Security-2] 電子投票 E-Voting

E-Voting

Notes from RWTH Aachen University course
“IT security 2” Wintersemester 2019/20
professor: Meyer, Ulrike Michaela

Security of (E)-Voting

was each vote captured correctly?
was each vote counted correctly?
Can the tally be independently verified?
Is each vote anonymous
Can anyone sell their vote?
Can voters be coered(被要脅) to vote in a particular way?
其他voting的優點
- Optical scanners
  - 避免miscounting
- Direct recording electronic voting system
  - 減少 voters’ error
  - 使 different disabilities 也可以投
- Internet voting
  - convenient
  - disabilities

Three Ballot Voting

paper based system 用電子計票
Goal
- 不用 cryptography 但盡可能達到越多 security properties
  因 cryptography 難理解，難被大家信任
basic idea
- 三張選票
- 不想要的候選人三張加總為1票
- 想要的候選人三張加總為2票
operation
- 投票者可以拿一張的選票備份
- 檢查serial number
- fake vote可以有最多1/3的機率被檢查到(如果voters都有檢查備份)
weakness
- 需要trust裝置
- votes pattern 的選擇要夠random
- Usability 差: 即使MIT學生也覺得confused
- serial number 被禁止：不能 link 選票和人

Bingo Voting

based on trusted random number generator
用 voting machine
coercion(強迫) impossible
cryptographic protocols
Commitment scheme
1. commitment
  - commitment \(c\) 由 message \(m\) 計算而來
  - 由 \(c\) 不能得知 \(m\)
2. open/ unveil
  - \(m\) 和 random number 公布
  - 每個人都可以 check \(c\) 是 \(m\) 的 commitment
- commitment 的性質
  - Hiding: 由 \(c\) 不能知道 \(m\)
  - Blinding: 給定 \(c\) 和 \(m\)，不能知道另一個 \(m'\neq m\) 使得 commitment 為 \(c\)
- Pedersen Commitments
  - 基於 discrete logarithm problem
  - 要 commit \(m\) 及 random number \(r\)
  - \(c=h^mg^r\)
  - binding property:
    - 假設有 \(m',r'\)
    - \(c=h^{m'}g^{r'}\)
    - \(log_g(h)=(r-r')(m-m')^{-1}\text{ mod }q\)
    - committing entity 知道 \(log_g(h)\)
  - hiding property:
    - \(r\) random
    - \(g^r\) random
    - \(c=h^mg^r\) random
    - 因此不能從 \(c\) 知道 \(m\)
  - Masking
    - 新的 commitment
    - 隨機一 \(s\)
    - 計算 \(c'=cg^s\)
    - \(c'=h^mg^{r+s}\)
Voting

voter在機器前選擇自己的候選人
對那個候選人產生一組新的 random number
機器印出候選人和 random number 的 pair
其餘沒有被選到的候選人的 random number 為機器原本就產生的
檢查 receipt 中有被改過的 random number 就是自己選的候選人

Counting
- 公開沒有被選到的候選人的 Dummy-votes
Pederson commitments in Bingo Voting
- 證明只有 \(L-1\) 組 dummy votes 被用
  ( \(L\) 為候選人個數)
- 公布 \(C=(P,r)\) 真正選擇的候選人
- 和 \(L-1\) (list1) 的 commitment
- 用 Mask 產生 list2
- 再 Mask 一次產生 list3
- 擲銅板決定公布 list1 / list2 的關係或 list2 / list3 的關係
Problems
- 使用者要相信 cryptographic protocol
- implementation 可能會有非預期的漏洞 (需要 open source)

Scantegrity

how it work?

用 human readible 和 machine readible serial number
得到 serial number 之後可以驗票
選票上的 letter 不能和候選人相關
公開後可以知道 serial number 和選擇的 letter

sereal number: \(1234\)
letter: \(A\)
candidate: \(Bob\)

Readings

Ross Anderson: “Security Engineering” § Chapter 23, p. 759 – 763

Ron Rivest: “Three Ballot”, 2006

Jens-Matthias Bohli, Jörn Müller-Quade and Stefan Röhrich: “Bingo Voting Secure

and Coercion-Free Voting Using a Trusted Random Number Generator ”, 2007

David Chaum et al.: “Scantegrity End-to-End Voter-Verifiable Optical-Scan Voting”,

2008

Jonathan Bannet et al.: “Hack-a-Vote: Security Issues with Electronic Voting

Systems” 2004

David Wagner: “Report on the California top-to-bottom review”, 2007

More details on the code review of the three commercial systems can be found here

ITVV