More Web Proxy on the site http://driver.im/

research-article

Measuring vote privacy, revisited

Authors:

David Bernhard,

Véronique Cortier,

Olivier Pereira,

Bogdan WarinschiAuthors Info & Claims

CCS '12: Proceedings of the 2012 ACM conference on Computer and communications security

Pages 941 - 952

https://doi.org/10.1145/2382196.2382295

Published: 16 October 2012 Publication History

Abstract

We propose a new measure for privacy of votes. Our measure relies on computational conditional entropy, an extension of the traditional notion of entropy that incorporates both information-theoretic and computational aspects. As a result, we capture in a unified manner privacy breaches due to two orthogonal sources of insecurity: combinatorial aspects that have to do with the number of participants, the distribution of their votes and published election outcome as well as insecurity of the cryptography used in an implementation.

Our privacy measure overcomes limitations of two previous approaches to defining vote privacy and we illustrate its applicability through several case studies. We offer a generic way of applying our measure to a large class of cryptographic protocols that includes the protocols implemented in Helios. We also describe a practical application of our metric on Scantegrity audit data from a real election.

References

[1]

B. Adida. Helios: Web-based Open-Audit Voting. In 17th USENIX Security Symposium, pages 335--348, 2008. Helios website: http://heliosvoting.org.

Digital Library

[2]

B. Adida, O. de Marneffe, O. Pereira, and J.-J. Quisquater. Electing a University President Using Open-Audit Voting: Analysis of Real-World Use of Helios. In Electronic Voting Technology Workshop/Workshop on Trustworthy Elections. Usenix, Aug. 2009.

Digital Library

[3]

J. Benaloh. Verifiable secret-ballot elections. Technical Report 561, Yale University Department of Computer Science, September 1987.

[4]

J. Benaloh and D. Tuinstra. Receipt-free secret-ballot elections. In 26th ACM Symposium on Theory of Computing, pages 544--553, 1994.

Digital Library

[5]

D. Bernhard, V. Cortier, O. Pereira, B. Smyth, and B. Warinschi. Adapting helios for provable ballot secrecy. In Springer, editor, 16th European Symposium on Research in Computer Security (ESORICS'11), volume 6879 of LNCS, 2011.

Digital Library

[6]

P. Bulens, D. Giry, and O. Pereira. Running mixnet-based elections with Helios. In Electronic Voting Technology Workshop/Workshop on Trustworthy Elections. Usenix, 2011.

Digital Library

[7]

R. Carback, D. Chaum, J. Clark, J. Conway, A. Essex, P. S. Herrnson, T. Mayberry, S. Popoveniuc, R. L. Rivest, E. Shen, A. T. Sherman, and P. L. Vora. Scantegrity II Municipal Election at Takoma Park: The First E2E Binding Governmental Election with Ballot Privacy. In USENIX Security Symposium, pages 291--306. USENIX Association, 2010.

Digital Library

[8]

K. Chatzikokolakis, C. Palamidessi, and P. Panangaden. Anonymity protocols as noisy channels. Information and Computation, 2-4(206):378--401, 2008.

Digital Library

[9]

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

Digital Library

[10]

D. Chaum, A. Essex, R. Carback, J. Clark, S. Popoveniuc, A. Sherman, and P. Vora. Scantegrity: End-to-End Voter-Verifiable Optical-Scan Voting. IEEE Security and Privacy, 6(3):40--46, 2008.

Digital Library

[11]

M. R. Clarkson, S. Chong, and A. C. Myers. Civitas: Toward a Secure Voting System. In 29th Security and Privacy Symposium (S&P'08). IEEE, 2008.

Digital Library

[12]

J. Cohen (Benaloh) and M. Fischer. A robust and verifiable cryptographically secure election scheme. In 26th Symposium on Foundations of Computer Science., pages 372--382, Portland, OR, 1985. IEEE.

Digital Library

[13]

S. Delaune, S. Kremer, and M. D. Ryan. Verifying privacy-type properties of electronic voting protocols. Journal of Computer Security, 17(4):435--487, 2009.

[14]

Y. Dodis, R. Ostrovsky, L. Reyzin, and A. Smith. Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. SIAM Journal of Computing, 38(1):97--139, 2008.

Digital Library

[15]

C. Dwork. Differential privacy. In Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, volume 4052 of LNCS, pages 1--12. Springer, 2006.

Digital Library

[16]

J. Furukawa, K. Mori, and K. Sako. An implementation of a mix-net based network voting scheme and its use in a private organization. In Towards Trustworthy Elections, volume 6000 of LNCS, pages 141--154. Springer, 2010.

Digital Library

[17]

C. Gentry and D. Wichs. Separating succint non-interactive arguments from all falsifiable assumptions. In 43rd ACM Symposium on Theory of Computing, pages 99--108, 2011.

Digital Library

[18]

O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game: A completeness theorem for protocols with honest majority. In 19th Annual ACM Symposium on the Theory of Computing (STOC), pages 218--229. ACM Press, 1987.

Digital Library

[19]

A. Juels, D. Catalano, and M. Jakobsson. Coercion-Resistant Electronic Elections. In 4th Workshop on Privacy in the Electronic Society (WPES 2005), pages 61--70. ACM, 2005.

Digital Library

[20]

A. Juels and M. Szydlo. A two-server, sealed-bid auction protocol. In 6th international conference on Financial cryptography (FC'02), pages 72--86. Springer, 2003.

Digital Library

[21]

R. Küsters, T. Truderung, and A. Vogt. A Game-Based Definition of Coercion-Resistance and its Applications. In 23rd IEEE Computer Security Foundations Symposium (CSF'10), pages 122--136. IEEE, 2010.

Digital Library

[22]

R. Küsters, T. Truderung, and A. Vogt. Proving Coercion-Resistance of Scantegrity II. In 12th International Conference on Information and Communications Security (ICICS 2010), volume 6476 of LNCS, pages 281--295, 2010.

Digital Library

[23]

R. Küsters, T. Truderung, and A. Vogt. Verifiability, Privacy, and Coercion-Resistance: New Insights from a Case Study. In IEEE Symposium on Security and Privacy (S&P 2011), pages 538--553. IEEE Computer Society, 2011.

Digital Library

[24]

T. Moran and M. Naor. Receipt-Free Universally-Verifiable Voting with Everlasting Privacy. In 26th International Cryptology Conference (CRYPTO'06), volume 4117 of LNCS, pages 373--392. Springer, 2006.

Digital Library

[25]

M. Naor, B. Pinkas, and R. Sumner. Privacy preserving auctions and mechanism design. In 1st ACM conf. on Electronic Commerce, 1999.

Digital Library

[26]

A. Rényi. On measures of information and entropy. In 4th Berkeley Symposium on Mathematics, Statistics and Probability, pages 547--561, 1960.

[27]

L. Reyzin. Some notions of entropy for cryptography - (invited talk). In Information Theoretic Security -- ICITS, pages 138--142, 2011.

Digital Library

[28]

R. L. Rivest and W. D. Smith. ThreeVotingProtocols: ThreeBallot, VAV, and Twin. In Electronic Voting Technology Workshop (EVT 2007), 2007.

Digital Library

[29]

P. Ryan, D. Bismark, J. Heather, S. Schneider, and Z. Xia. The prêt à voter verifiable election system. IEEE Transactions on Information Forensics and Security, 4:662--673, 2009.

Digital Library

[30]

K. Sako and J. Kilian. Receipt-free mix-type voting scheme - a practical solution to the implementation of a voting booth. In Advances in Cryptology - EUROCRYPT '95, volume 921 of LNCS, pages 393--403. Springer, 1995.

Digital Library

[31]

C. Shannon. A mathematical theory of communication. Bell System Technical Journal, pages 379--423 and 623--656, 1948.

[32]

G. Smith. Quantifying information flow using min-entropy. In 8th International Conference on Quantitative Evaluation of SysTems (QEST'11), invited paper, pages 159--167, 2011.

Digital Library

[33]

D. Unruh and J. Müller-Quade. Universally Composable Incoercibility. In 30th International Cryptology Conference (CRYPTO'10), volume 6223 of LNCS, pages 411--428. Springer, 2010.

Digital Library

Cited By

Mestel DMüller JReisert P(2023)How efficient are replay attacks against vote privacy? A formal quantitative analysis1Journal of Computer Security10.3233/JCS-23004731:5(421-467)Online publication date: 13-Oct-2023
https://doi.org/10.3233/JCS-230047
Mestel DMüller JReisert P(2022)How Efficient are Replay Attacks against Vote Privacy? A Formal Quantitative Analysis2022 IEEE 35th Computer Security Foundations Symposium (CSF)10.1109/CSF54842.2022.9979167(179-194)Online publication date: Aug-2022
https://doi.org/10.1109/CSF54842.2022.9979167
Ryan PRoenne POstrev DEl Orche FSoroush NStark P(2021)Who Was that Masked Voter? The Tally Won’t Tell!Electronic Voting10.1007/978-3-030-86942-7_8(106-123)Online publication date: 28-Sep-2021
https://doi.org/10.1007/978-3-030-86942-7_8
Show More Cited By

Index Terms

Measuring vote privacy, revisited

Recommendations

Verifiability, Privacy, and Coercion-Resistance: New Insights from a Case Study
SP '11: Proceedings of the 2011 IEEE Symposium on Security and Privacy

In this paper, we present new insights into central properties of voting systems, namely verifiability, privacy, and coercion-resistance. We demonstrate that the combination of the two forms of verifiability considered in the literature -- individual ...
Securing optical-scan voting
Towards Trustworthy Elections

This paper presents a method for adding end-to-end verifiability to any optical-scan vote counting system. A serial number and set of letters, paired with every candidate, are printed on each optical-scan ballot. The letter printed next to the candidate(...
Relations Between Privacy, Verifiability, Accountability and Coercion-Resistance in Voting Protocols
Applied Cryptography and Network Security
Abstract
This paper studies quantitative relationships between privacy, verifiability, accountability, and coercion-resistance of voting protocols. We adapt existing definitions to make them better comparable with each other and determine which bounds a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '12: Proceedings of the 2012 ACM conference on Computer and communications security

October 2012

1088 pages

ISBN:9781450316514

DOI:10.1145/2382196

General Chair:
Ting Yu
North Carolina State University, USA
,
Program Chairs:
George Danezis
Microsoft Research Cambridge, UK
,
Virgil Gligor
Carnegie Mellon University, USA

Copyright © 2012 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

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 October 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CCS'12

Sponsor:

SIGSAC

CCS'12: the ACM Conference on Computer and Communications Security

October 16 - 18, 2012

North Carolina, Raleigh, USA

Acceptance Rates

Overall Acceptance Rate 1,234 of 6,846 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

21
Total Citations
View Citations
429
Total Downloads

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

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mestel DMüller JReisert P(2023)How efficient are replay attacks against vote privacy? A formal quantitative analysis1Journal of Computer Security10.3233/JCS-23004731:5(421-467)Online publication date: 13-Oct-2023
https://doi.org/10.3233/JCS-230047
Mestel DMüller JReisert P(2022)How Efficient are Replay Attacks against Vote Privacy? A Formal Quantitative Analysis2022 IEEE 35th Computer Security Foundations Symposium (CSF)10.1109/CSF54842.2022.9979167(179-194)Online publication date: Aug-2022
https://doi.org/10.1109/CSF54842.2022.9979167
Ryan PRoenne POstrev DEl Orche FSoroush NStark P(2021)Who Was that Masked Voter? The Tally Won’t Tell!Electronic Voting10.1007/978-3-030-86942-7_8(106-123)Online publication date: 28-Sep-2021
https://doi.org/10.1007/978-3-030-86942-7_8
McIver ARabehaja TWen RMorgan C(2017)Privacy in electionsJournal of Information Security and Applications10.1016/j.jisa.2017.08.00336:C(112-126)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1016/j.jisa.2017.08.003
Ashur TDunkelman OTalmon N(2017)Breaching the Privacy of Israel’s Paper Ballot Voting SystemElectronic Voting10.1007/978-3-319-52240-1_7(108-124)Online publication date: 26-Jan-2017
https://doi.org/10.1007/978-3-319-52240-1_7
Didona DDiegues NKermarrec AGuerraoui RNeves RRomano P(2016)ProteusTMACM SIGARCH Computer Architecture News10.1145/2980024.287238544:2(757-771)Online publication date: 25-Mar-2016
https://dl.acm.org/doi/10.1145/2980024.2872385
Zhang TLee DJung C(2016)TxRaceACM SIGARCH Computer Architecture News10.1145/2980024.287238444:2(159-173)Online publication date: 25-Mar-2016
https://dl.acm.org/doi/10.1145/2980024.2872384
Haines TBoyen X(2016)VOTORProceedings of the Australasian Computer Science Week Multiconference10.1145/2843043.2843362(1-13)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1145/2843043.2843362
Norris BDemsky B(2016)A Practical Approach for Model Checking C/C++11 CodeACM Transactions on Programming Languages and Systems10.1145/280688638:3(1-51)Online publication date: 2-May-2016
https://dl.acm.org/doi/10.1145/2806886
Yu S(2016)Big Privacy: Challenges and Opportunities of Privacy Study in the Age of Big DataIEEE Access10.1109/ACCESS.2016.25770364(2751-2763)Online publication date: 2016
https://doi.org/10.1109/ACCESS.2016.2577036
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