Article

Split-ballot voting: everlasting privacy with distributed trust

Authors:

Moni NaorAuthors Info & Claims

CCS '07: Proceedings of the 14th ACM conference on Computer and communications security

Pages 246 - 255

https://doi.org/10.1145/1315245.1315277

Published: 28 October 2007 Publication History

Abstract

In this paper we propose a new voting protocol with desirable security properties. The voting stage of the protocol can be performed by humans without computers; it provides every voter with the means to verify that all the votes were counted correctly (universal verifiability) while preserving ballot secrecy. The protocol has "everlasting privacy": even a computationally unbounded adversary gains no information about specific votes from observing the protocol's output. Unlike previous protocols with these properties, this protocol distributes trust between two authorities: a single corrupt authority will not cause voter privacy to be breached. Finally, the protocol is receipt-free: a voter cannot prove how she voted even she wants to do so. We formally prove the security of the protocol in the Universal Composability framework, based on number-theoretic assumptions.

References

[1]

B. Adida and R. L. Rivest. Scratch & vote: self-contained paper-based cryptographic voting. In WPES '06, pages 29--40, 2006.

Digital Library

[2]

Y. Aumann, Y. Z. Ding, and M. O. Rabin. Everlasting security in the bounded storage model. IEEE Trans. on Information Theory, 48(6):1668--1680, 2002.

Digital Library

[3]

J. Benaloh and D. Tuinstra. Receipt-free secret-ballot elections. In STOC '94, pages 544--553, 1994.

Digital Library

[4]

J. W. Bryans and P. Y. A. Ryan. A simplified version of the Chaum voting scheme. Technical Report CS-TR 843, University of Newcastle, 2004.

[5]

R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. Cryptology ePrint Archive, Report 2000/067, 2000.

[6]

R. Canetti and R. Gennaro. Incoercible multiparty computation. In FOCS '96, pages 504--513.

Digital Library

[7]

D. Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the ACM, 24(2):84--88, 1981.

Digital Library

[8]

D. Chaum. E-voting: Secret-ballot receipts: True voter-verifiable elections. IEEE Security & Privacy, 2(1):38--47, Jan./Feb. 2004.

Digital Library

[9]

D. Chaum, 2006. http://punchscan.org/.

[10]

J. D. Cohen (Benaloh) and M. J. Fischer. A robust and verifiable cryptographically secure election scheme. In FOCS '85, pages 372--382.

Digital Library

[11]

R. Cramer, M. Franklin, B. Schoenmakers, and M. Yung. Multi-authority secret-ballot elections with linear work. In Eurocrypt '96, pages 72--83.

Digital Library

[12]

R. Cramer, R. Gennaro, and B. Schoenmakers. A secure and optimally efficient multi-authority election scheme. In Eurocrypt '97, pages 103--118.

Digital Library

[13]

A. Fujioka, T. Okamoto, and K. Ohta. A practical secret voting scheme for large scale elections. In AUSCRYPT '92, pages 244--251.

Digital Library

[14]

M. Hirt and K. Sako. Efficient receipt-free voting based on homomorphic encryption. In Eurocrypt '00, pages 539+.

Digital Library

[15]

T. Moran and M. Naor. Basing cryptographic protocols on tamper-evident seals. In ICALP '05, pages 285--297.

Digital Library

[16]

T. Moran and M. Naor. Receipt-free universally-verifiable voting with everlasting privacy. In CRYPTO, pages 373--392, 2006. http://www.wisdom.weizmann.ac.il/~talm/papers/MN06-voting.pdf.

Digital Library

[17]

M. Naor and A. Shamir. Visual cryptography. In Eurocrypt '94, volume 950 of LNCS, pages 1--12, 1995.

[18]

C. A. Neff. Practical high certainty intent verification for encrypted votes, October 2004. http://www.votehere.net/vhti/documentation/vsv-2.0.3638.pdf.

[19]

S. Popoveniuc and B. Hosp. An introduction to punchscan, 2006. http://punchscan.org/papers/popoveniuc_hosp_punchscan_introduction.pdf.

[20]

M. O. Rabin. Transaction protection by beacons. J.Computer and System Sciences, 27(2):256--267, 1983.

[21]

D. J. Reynolds. A method for electronic voting with coercion-free receipt. Presentation: http://www.win.tue.nl/~berry/fee2005/presentations/reynolds.ppt.

[22]

P. Y. A. Ryan. A variant of the Chaum voter-verifiable scheme. In WITS '05, pages 81--88, 2005.

Digital Library

[23]

A. Shamir. Cryptographers panel, RSA conference, 2006. Webcast: http://media.omediaweb.com/rsa2006/1_5/1_5_High.asx.

Cited By

Miyahara DRobert LLafourcade PMizuki T(2024)ZKP Protocols for Usowan, Herugolf, and Five CellsTsinghua Science and Technology10.26599/TST.2023.901015329:6(1651-1666)Online publication date: Dec-2024
https://doi.org/10.26599/TST.2023.9010153
Robert LMiyahara DLafourcade PMizuki T(2023)Hide a Liar: Card-Based ZKP Protocol for UsowanTheory and Applications of Models of Computation10.1007/978-3-031-20350-3_17(201-217)Online publication date: 1-Jan-2023
https://doi.org/10.1007/978-3-031-20350-3_17
Boyen XHaines TMüller J(2021)Epoque: Practical End-to-End Verifiable Post-Quantum-Secure E-Voting2021 IEEE European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP51992.2021.00027(272-291)Online publication date: Sep-2021
https://doi.org/10.1109/EuroSP51992.2021.00027
Show More Cited By

Index Terms

Split-ballot voting: everlasting privacy with distributed trust

Recommendations

Split-ballot voting: Everlasting privacy with distributed trust

In this article, we propose a new voting protocol with several desirable security properties. The voting stage of the protocol can be performed by humans without computers; it provides every voter with the means to verify that all the votes were counted ...
A Receipt-Free Punch-Hole Ballot Electronic Voting Scheme
SITIS '07: Proceedings of the 2007 Third International IEEE Conference on Signal-Image Technologies and Internet-Based System

The punch-hole ballot electronic voting protocol is a special version of the e-voting paradigms based on homomorphic encryption. Assume that there are L candidates and a voter can select K distinct candidates, the punch-hole ballot is represented as a ...
Ballot length in instant runoff voting
AAAI'23/IAAI'23/EAAI'23: Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence

Instant runoff voting (IRV) is an increasingly-popular alternative to traditional plurality voting in which voters submit rankings over the candidates rather than single votes. In practice, elections using IRV often restrict the ballot length, the number ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '07: Proceedings of the 14th ACM conference on Computer and communications security

October 2007

628 pages

ISBN:9781595937032

DOI:10.1145/1315245

General Chair:
Peng Ning
NC State University, USA
,
Program Chairs:
Sabrina De Capitani di Vimercati
University of Milan, Italy
,
Paul Syverson
Naval Research Laboratory, USA

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 October 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

CCS07

Sponsor:

CCS07: 14th ACM Conference on Computer and Communications Security 2007

November 2 - October 31, 2007

Virginia, Alexandria, USA

Acceptance Rates

CCS '07 Paper Acceptance Rate 55 of 302 submissions, 18%;

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
586
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)2

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Miyahara DRobert LLafourcade PMizuki T(2024)ZKP Protocols for Usowan, Herugolf, and Five CellsTsinghua Science and Technology10.26599/TST.2023.901015329:6(1651-1666)Online publication date: Dec-2024
https://doi.org/10.26599/TST.2023.9010153
Robert LMiyahara DLafourcade PMizuki T(2023)Hide a Liar: Card-Based ZKP Protocol for UsowanTheory and Applications of Models of Computation10.1007/978-3-031-20350-3_17(201-217)Online publication date: 1-Jan-2023
https://doi.org/10.1007/978-3-031-20350-3_17
Boyen XHaines TMüller J(2021)Epoque: Practical End-to-End Verifiable Post-Quantum-Secure E-Voting2021 IEEE European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP51992.2021.00027(272-291)Online publication date: Sep-2021
https://doi.org/10.1109/EuroSP51992.2021.00027
Ge HChau SGonsalves VLi HWang TZou XLi NBalenson D(2019)KoinoniaProceedings of the 35th Annual Computer Security Applications Conference10.1145/3359789.3359804(270-285)Online publication date: 9-Dec-2019
https://dl.acm.org/doi/10.1145/3359789.3359804
Ribeiro LMarcelino AGarcia GGoncalves DTarelho LCorrea LChapetta WDe Oliveira Sa AMachado R(2018)True Random Number Generators for Batch Control Sampling in Smart Factories2018 Workshop on Metrology for Industry 4.0 and IoT10.1109/METROI4.2018.8428319(213-217)Online publication date: Apr-2018
https://doi.org/10.1109/METROI4.2018.8428319
Costa NMartínez RMorillo P(2017)Proof of a Shuffle for Lattice-Based CryptographySecure IT Systems10.1007/978-3-319-70290-2_17(280-296)Online publication date: 4-Nov-2017
https://doi.org/10.1007/978-3-319-70290-2_17
Yang NClark J(2017)Practical Governmental Voting with Unconditional Integrity and PrivacyFinancial Cryptography and Data Security10.1007/978-3-319-70278-0_27(434-449)Online publication date: 19-Nov-2017
https://doi.org/10.1007/978-3-319-70278-0_27
Locher PHaenni R(2016)Receipt-free remote electronic elections with everlasting privacyAnnals of Telecommunications10.1007/s12243-016-0519-671:7-8(323-336)Online publication date: 12-May-2016
https://doi.org/10.1007/s12243-016-0519-6
Bernhard DCortier VGalindo DPereira OWarinschi B(2015)SoKProceedings of the 2015 IEEE Symposium on Security and Privacy10.1109/SP.2015.37(499-516)Online publication date: 17-May-2015
https://dl.acm.org/doi/10.1109/SP.2015.37
Andrychowicz MDziembowski S(2015)PoW-Based Distributed Cryptography with No Trusted SetupAdvances in Cryptology -- CRYPTO 201510.1007/978-3-662-48000-7_19(379-399)Online publication date: 1-Aug-2015
https://doi.org/10.1007/978-3-662-48000-7_19
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents