Elections in the Post-Quantum Era: Is the Complexity Shield Strong Enough?

• URL: http://arxiv.org/abs/2403.05273v1
• Date: Fri, 8 Mar 2024 12:52:11 GMT
• Title: Elections in the Post-Quantum Era: Is the Complexity Shield Strong Enough?
• Authors: \v{S}imon Schierreich
• Abstract summary: We consider quantum computers to be a new threat to the complexity shield described above. We provide an overview of possible attacks on election, discuss the abilities of quantum computing, and chart possible directions for future research in this area.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The election, a cornerstone of democracy, is one of the best-recognizable symbols of democratic governance. Voters' confidence in elections is essential, and these days, we can watch practically in live broadcast what consequences distrust in the fairness of elections may have. From the times of the celebrated Gibbard-Satterthwaite theorem, it is well-known in the social-choice community that most voting systems are vulnerable to the efforts of various players to influence elections. Luckily for us, computing such influence to affect election outcomes is a hard problem from the computational complexity perspective. This intractability is regarded as a ``complexity shield'' that secures voting rules against this malicious behavior. In this work, we consider quantum computers to be a new threat to the complexity shield described above, as they break out of standard computing paradigms and unlock additional computational resources. To this end, we provide an overview of possible attacks on election, discuss the abilities of quantum computing, and chart possible directions for future research in this area.

Related papers

• Improving the Computational Efficiency of Adaptive Audits of IRV Elections [54.427049258408424]
  AWAIRE can audit IRV contests with any number of candidates, but the original implementation incurred memory and computation costs that grew superexponentially with the number of candidates. This paper improves the algorithmic implementation of AWAIRE in three ways that make it practical to audit IRV contests with 55 candidates, compared to the previous 6 candidates.
  arXiv  Detail & Related papers  (2024-07-23T13:28:00Z)
• Representation Bias in Political Sample Simulations with Large Language Models [54.48283690603358]
  This study seeks to identify and quantify biases in simulating political samples with Large Language Models. Using the GPT-3.5-Turbo model, we leverage data from the American National Election Studies, German Longitudinal Election Study, Zuobiao dataset, and China Family Panel Studies.
  arXiv  Detail & Related papers  (2024-07-16T05:52:26Z)
• Quantum-Enhanced Secure Approval Voting Protocol [0.0]
  This paper introduces a quantum voting protocol, a blend of quantum principles (entanglement and superposition), blockchain technology, and digital signatures. The protocol is tested on IBM quantum hardware, achieving impressively low error rates of just 1.17% in a four-candidate election.
  arXiv  Detail & Related papers  (2024-06-28T08:20:25Z)
• Learning to Manipulate under Limited Information [44.99833362998488]
  We trained over 70,000 neural networks of 26 sizes to manipulate against 8 different voting methods. We find that some voting methods, such as Borda, are highly manipulable by networks with limited information, while others, such as Instant Runoff, are not.
  arXiv  Detail & Related papers  (2024-01-29T18:49:50Z)
• Adaptively Weighted Audits of Instant-Runoff Voting Elections: AWAIRE [61.872917066847855]
  Methods for auditing instant-runoff voting (IRV) elections are either not risk-limiting or require cast vote records (CVRs), the voting system's electronic record of the votes on each ballot. We develop an RLA method that uses adaptively weighted averages of test supermartingales to efficiently audit IRV elections when CVRs are not available.
  arXiv  Detail & Related papers  (2023-07-20T15:55:34Z)
• Accelerating Voting by Quantum Computation [35.03314687289671]
  We propose a quantum-accelerated voting algorithm that can be applied to any anonymous voting rule. Our algorithm outputs the correct winner with high probability in $Thetaleft(fracntextMOVright)$ time.
  arXiv  Detail & Related papers  (2023-01-08T07:29:38Z)
• Anonymous voting scheme using quantum assisted blockchain [0.39146761527401425]
  We propose an anonymous voting scheme based on quantum assisted blockchain. The voting scheme is auditable and can be implemented using the currently available technology.
  arXiv  Detail & Related papers  (2022-06-07T11:07:28Z)
• Towards Secure Virtual Elections: Multiparty Computation of Order Based Voting Rules [5.156484100374059]
  One of the main challenges in e-voting systems is to certify that the computed results are consistent with the cast ballots. We propose a secure voting protocol for elections governed by order-based voting rules. Our protocol offers perfect ballot secrecy, in the sense that it issues only the required output, while no other information on the cast ballots is revealed.
  arXiv  Detail & Related papers  (2022-05-21T12:17:21Z)
• Expected Frequency Matrices of Elections: Computation, Geometry, and Preference Learning [58.23459346724491]
  We use the "map of elections" approach of Szufa et al. (AAMAS 2020) to analyze several well-known vote distributions. We draw the "skeleton map" of distributions, evaluate its robustness, and analyze its properties.
  arXiv  Detail & Related papers  (2022-05-16T17:40:22Z)
• Obvious Manipulability of Voting Rules [105.35249497503527]
  The Gibbard-Satterthwaite theorem states that no unanimous and non-dictatorial voting rule is strategyproof. We revisit voting rules and consider a weaker notion of strategyproofness called not obvious manipulability.
  arXiv  Detail & Related papers  (2021-11-03T02:41:48Z)
• An algorithm for a fairer and better voting system [0.0]
  This article is about a novel, better ranked voting system that aims to solve the problem of finding the best candidate to represent the voters. We have the source code on GitHub, for making realistic simulations of elections, based on artificial intelligence. We have convincing evidence that our algorithm is better than Instant-Runoff Voting, Preferential Block Voting, Single Transferable Vote, and First Past The Post.
  arXiv  Detail & Related papers  (2021-10-13T22:34:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.