Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2403.05273 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914708967129088 |
|---|---|
| author | Schierreich, Šimon |
| author_facet | Schierreich, Šimon |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_05273 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Elections in the Post-Quantum Era: Is the Complexity Shield Strong Enough? Schierreich, Šimon Cryptography and Security Computers and Society Computer Science and Game Theory 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. |
| title | Elections in the Post-Quantum Era: Is the Complexity Shield Strong Enough? |
| topic | Cryptography and Security Computers and Society Computer Science and Game Theory |
| url | https://arxiv.org/abs/2403.05273 |