펀치스캔

펀치스캔

개발자	리처드 카백, 데이비드 차움, 제레미 클라크, 알렉스 에섹스, 스테판 포포베니우크.
안정적 해제	1.0 (2006년 11월 2일) [±]
릴리스 미리 보기	1.5 (2007년 7월 16일) [±]
기록 위치	자바
운영 체제	크로스 플랫폼
다음에서 사용 가능	영어
유형	개표 시스템
면허증	수정된 BSD 라이센스
웹사이트	http://punchscan.org/

펀치스캔(Punchscan)은 암호학자 데이비드 차움(David Chaum)이 발명한 광학 스캔 투표 집계 시스템이다. 펀치스캔은 무결성, 프라이버시, 투명성을 제공하도록 설계되었다. 이 시스템은 유권자 검증이 가능하고, 엔드투엔드(E2E) 감사 메커니즘을 제공하며, 각 투표자에게 투표 영수증을 발급한다. 이 시스템은 2007년 대학 투표 시스템 대회에서 대상을 받았다.

Punchscan이 통합한 컴퓨터 소프트웨어는 오픈소스다; 소스 코드는 2006년 11월 2일 개정된 BSD 라이선스에 의해 공개되었다.^[1] 그러나 Punchscan은 소프트웨어 독립적이다. Punchscan은 DREE 투표 기계와 같은 소프트웨어 보안에 의존하지 않고 암호화 기능으로부터 그것의 보안을 끌어낸다. 이러한 이유로, Punchscan은 마이크로소프트 윈도우와 같은 폐쇄적인 소스 운영 체제에서 실행될 수 있으며, 여전히 무조건적인 무결성을 유지할 수 있다.

펀치스캔 팀은 추가 기여자들과 함께 그 이후 Scantegrity를 개발했다.

투표절차

펀치스캔 투표용지에는 두 겹의 종이가 있다. 맨 위 층에는 후보자 이름 옆에 기호나 글자가 적혀 있다. 후보 명단 아래에는 투표용지 상단 층에 동그란 구멍이 줄줄이 나 있다. 아래층의 구멍 안에는 해당 기호가 인쇄되어 있다.

후보에게 표를 던지려면 유권자가 후보 이름 옆에 기호에 해당하는 기호가 있는 구멍을 찾아야 한다. 이 구멍은 빙고식 잉크 도버로 표시되어 있는데, 의도적으로 구멍보다 크다. 그런 다음 투표자는 투표용지를 분리하고 영수증으로 보관할 상단 또는 하단 층 중 하나를 선택한 후 다른 층을 채 썬다. 투표소에서 영수증을 스캔하여 표를 구한다.

후보명 옆에 있는 기호 순서는 각 투표용지에 대해 무작위로 생성되므로 투표용지에 따라 차이가 있다. 구멍에 있는 기호의 순서도 마찬가지야. 이 때문에 영수증에는 어느 후보에게 표를 던졌는지를 판단할 만한 충분한 정보가 담겨 있지 않다. 상단 층을 유지하면 구멍을 통한 기호 순서는 알 수 없다. 맨 아래 층을 유지하면 후보명 옆에 있는 기호 순서는 알 수 없다. 따라서, 유권자는 그들이 어떻게 투표했는지 다른 사람에게 증명할 수 없으며, 이것은 투표 매수나 유권자의 위협을 막는다.

표 작성 절차

예를 들어, 앞의 도표와 같이 코카콜라와 펩시의 두 후보 선거를 생각해 보자. 후보자 이름 옆에 있는 글자의 순서는 A, B, B, A일 수 있다. 우리는 이 ${\displaystyle {주문}_{}}$을 P $1{\displaystyle {}_{}}$ ${\$}라고 부르고$,$ 이전 주문의 $경우{\displaystyle {}_{}}$ P ${\displaystyle {1\mathrm{}}_{}}$ ${\$}$$=0으로 하고, 후자의 ${\displaystyle {경우\mathrm{}}_{}}$ P 1$${\$displaystyle P_{$1$\}=$1로 한다. 그러므로

${\displaystyle P_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}$$: 후보 목록 옆의 기호 순서,

${\$$AB},{\mbox{B$$A$

마찬가지로 투표의 다른 부분에 대해서도 일반화할 수 있다.

${\displaystyle P_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}$$: 구멍을 통한 기호 순서,

${\$$AB},{\mbox{B$$A$

${\displaystyle P_{}}$ ${\displaystyle {3\mathrm{}}_{}}$ ${\$: 어떤 구멍이 표시되든지,

${\displaystyle P_{}}$ ${\displaystyle {3\mathrm{}}_{}\in \{0\},}$ ${\displaystyle 1}$ ${\displaystyle \}}$=${\displaystyle }${ ${\displaystyle \text{1st},}$ ${\displaystyle \text{2st}}$ ${\displaystyle \}}$ ${\$

${\displaystyle R}$ ${\displaystyle R}$: 투표 결과,

${\displaystyle R\in \{0,}$ ${\displaystyle 1}$ ${\displaystyle \}}$=${\displaystyle }${ ${\displaystyle \text{Coke}}$ ,${\displaystyle \text{펩시}}$ ${\displaystyle \}}$ ${\$

모든 투표용지 전체에 걸쳐 후보 이름의 순서가 고정되어 있다는 점에 유의하십시오. 투표 결과는 다음과 같이 직접 계산할 수 있다.

$displaystyle R=P_{1}+P_{2}+P_{3$$$$}}{\bmod{2}}\,}($등분 1)

그러나 투표용지 한 겹이 파쇄되면 ${\displaystyle {P\mathrm{}}_{}}$ $1{\displaystyle {}_{}}$ ${\$또는$$ ${\displaystyle {P\mathrm{}}_{}}$ $2{\displaystyle {}_{}}$ ${\$}}개가 파괴된다$$. 따라서 (스캔한) $영수증$에서 R ${\displaystyle R}$을(를) 계산하기에는 정보가 불충분하다. 선거 결과를 계산하기 위해 전자 데이터베이스를 사용한다.

선거 전에 데이터베이스는 일련의 열을 사용하여 생성된다. 데이터베이스의 각 행은 투표용지를 나타내며, 투표용지를 데이터베이스에 저장하는 순서는 뒤틀린다(각 후보가 기여할 수 있는 암호키를 사용). 첫 번째 열인 D ${\displaystyle {1\mathrm{}}_{}}$ ${\$}은(는$)$ 일련번호 순서를 섞었다. ${\displaystyle D_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ 키에서 생성된 유사란덤 비트스트림을 포함하며$$, 스트림 암호의 역할을 하게 된다. ${\displaystyle D_{}}$ ${\$는 중간 결과를 저장한다. ${\displaystyle D_{}}$ ${\displaystyle {4\mathrm{}}_{}}$ ${\$에는 다음과 같은 내용이 포함되어$$ 있다.

${\displaystyle D_{2}+D_{4}=P_{1}+P_{2}{\bmod{2}},}$

각 투표의 결과는 투표 순서가 다시 개편되는 $별도$의 $칼럼$ R {\디스플레이 스타일 $R}$에 저장된다$.$ 따라서 $D{\displaystyle {}_{}}$ ${\displaystyle {5\mathrm{}}_{}}$ ${\$는 결과가 배치될 $R{\displaystyle }$ ${\displaystyle R}$ 열에$$ 행 번호를 포함한다$$.

선거가 $실행$되고 P ${\displaystyle {3\mathrm{}}_{}}$ ${\$ 값이$$ 스캔된 후 $D{\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$ ${\$는 다음과 같이 계산된다$$.

${\displaystyle D_{3}=P_{3}+D_{2}{\bmod{2}}\,}$

그리고 그 결과는 다음과 같이 계산된다.

${\displaystyle R=D_{3}+D_{4}{\bmod{2}}\,}$

이것은 방정식 1과 같다.

${\displaystyle {\begin{aligned}R&=(D_{3})+D_{4}{\bmod {2}}\\&=(P_{3}+D_{2})+D_{4}{\bmod {2}}\\&=P_{3}+(D_{2}+D_{4}){\bmod {2}}\\&=P_{3}+(P_{1}+P_{2}){\bmod {2}}\end{aligned}}}$

결과란이 발행되고 투표용지가 뒤틀린 경우(두 번) 결과 열의 순서는 어떤 투표용지 번호에서 어떤 결과가 나왔는지 나타내지 않는다. 따라서 선거 당국은 일련번호까지 표를 추적할 수 없다.

일반화형

$n{\displaystyle }$ ${\displaystyle n}$명의$$ 후보가 있는 선거의 경우 modulo-n 방정식을 사용하여 위의 절차를 따른다.

기본 감사 절차

투표자의 투표용지 영수증에는 투표자가 어느 후보에게 투표했는지 표시되지 않으므로 비밀 정보가 아니다. 선거가 끝난 후, 선거 당국은 각 영수증의 이미지를 온라인에 게시할 것이다. 투표자는 일련번호를 입력하여 투표용지를 조회할 수 있으며, 선거 당국이 보유한 정보가 투표용지와 일치하는지 확인할 수 있다. 이렇게 하면 유권자는 자신의 투표용지가 의도대로 투표되었다고 확신할 수 있다.

유권자 또는 이해관계자는 또한 결과가 올바르게 계산되었는지 확인하기 위해 데이터베이스의 일부를 검사할 수 있다. 그들은 전체 데이터베이스를 검사할 수 없다. 그렇지 않으면 투표를 투표용 일련 번호와 연결할 수 있다. 그러나 데이터베이스의 절반은 사생활 침해 없이 안전하게 검사받을 수 있다. A random choice is made between opening ${\displaystyle \{D_{1},D_{2},D_{3}\}}$ or ${\displaystyle \{D_{3},D_{4},D_{5}\}}$ (this choice can be derived from the secret key or from a true random source, such as dice^[2] or the stock market^[3]). 이 절차를 통해 유권자는 모든 투표 용지가 투표로 계산되었다고 확신할 수 있다.

만약 모든 투표용지가 의도한 대로 주조되고 주조된다면, 모든 투표용지는 의도한 대로 계산된다. 따라서 선거의 청렴성은 매우 높은 확률로 증명될 수 있다.

추가 보안

펀치스캔 선거의 무결성을 더욱 높이기 위해, 완전히 부패한 선거 당국으로부터 보호하기 위한 몇 가지 추가 조치를 취할 수 있다.

다중 데이터베이스

데이터베이스에 있는$$ $D{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$ ${\displaystyle {D\mathrm{}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ $D{\displaystyle {}_{}}$ 5 ${\$가 모두 유사하게 생성되므로, 이들 열에 대해 서로 다른 랜덤 값으로 여러 데이터베이스를 작성할 수 있다. 각 데이터베이스는 다른 데이터베이스와 독립되어 있어 일부 데이터베이스는 전반부를 열고 검사할 수 있으며, 후반부는 다른 데이터베이스와 독립적이다. 각 데이터베이스는 동일한 최종 집계를 작성해야 한다. 따라서 선거 당국이 최종 집계를 왜곡하기 위해 데이터베이스를 조작하려면 각 데이터베이스를 조작해야 할 것이다. 감사에서 변조 사실이 밝혀질 확률은 독립 데이터베이스의 수에 따라 증가한다.

약속

선거 당국은 선거에 앞서 투표용지를 인쇄하고 데이터베이스를 작성한다. 이 작성 과정의 일부는 각 투표용지와 데이터베이스에 포함된 고유한 정보를 준수하는 것을 포함한다. 이것은 암호 단방향 함수를 정보에 적용함으로써 달성된다. 비록 이 기능의 결과인 약속은 공개되지만, 실제 약속된 정보는 봉인된 상태로 남아 있다. 기능이 일방적이기 때문에 공개적인 공약만 주어진다면 봉인된 투표용지의 정보를 결정하는 것은 계산적으로 불가능하다.

투표 검사

선거 전에, 투표 용지는 선거에 이용하려는 숫자보다 두 배나 더 많이 생산된다. 이들 투표지의 절반은 무작위로 선택된다(또는 각 후보가 투표용지의 일부를 선택할 수 있다). 이러한 선택된 투표용지에 해당하는 데이터베이스의 행을 확인하여 계산이 정확하고 변조되지 않았는지 확인할 수 있다. 선거 당국은 어떤 투표지를 선정할 것인지 알 수 없기 때문에, 이번 감사를 통과한다는 것은 데이터베이스가 매우 높은 확률로 잘 형성되어 있다는 것을 의미한다. 게다가, 투표 용지는 투표 용지가 정확할 가능성이 높은지 확인하기 위해 그들의 약속과 대조적으로 확인될 수 있다.

참고 항목

• 스트림 암호
• 약속 체계
• 영지식증거

참조

외부 링크

• 프로젝트 홈 페이지
• Vocomp Submission - 시스템의 모든 측면을 설명하는 80페이지의 포괄적인 문서
• Electronic Democracy — BBC 월드 디지털 플래닛 오디오 인터뷰(David Chaum)
• 모든 전자투표 카운트 만들기 — IEEE 스펙트럼.
• Punchscan을 사용하여 투명하고 개방된 투표: Part I 및 Part II
• 미래 시제 오디오 인터뷰는 데이비드 차움과의 미래형 오디오 인터뷰.